HihoCoder 119周网络流五·最大权闭合子图

正文索引 [隐藏]

题解
代码

传送门：http://hihocoder.com/contest/hiho119/problem/1

题解

最大权闭合子图建图，跑一边网络流

代码

//while(true) RP++;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
struct Dinic{
    const static int Maxn=500;
    const static int Maxm=Maxn*Maxn;
    const static int Inf=2100000000;
    int head[Maxn+5];
    int cur[Maxn+5];
    struct Edge{
        int v,nxt,f;
        Edge(){}
        Edge(int v0,int n0,int f0){
            v=v0;
            nxt=n0;
            f=f0;
        }
    };
    Edge e[Maxm*2+5];
    int nume;
    inline void init(){
        nume=1;
        memset(head,0,sizeof(head));
    }
    inline void insertEdge(int u,int v,int f){
        e[++nume]=Edge(v,head[u],f);
        head[u]=nume;
    }
    inline void addEdge(int u,int v,int f){
        insertEdge(u,v,f);
        insertEdge(v,u,0);
    }
    int dist[Maxn+5];
    queue<int> que;
    int src,sink;
    inline bool bfs(){
        while(!que.empty())que.pop();
        memset(dist,-1,sizeof(dist));
        dist[src]=0;
        que.push(src);
        while(!que.empty()){
            int now=que.front();
            que.pop();
            for (int i=head[now];i;i=e[i].nxt){
                if (e[i].f>0 && dist[e[i].v]==-1){
                    dist[e[i].v]=dist[now]+1;
                    que.push(e[i].v);
                }
            }
        }
        return dist[sink]!=-1;
    }
    int dfs(int x,int delta){
        if (x==sink){
            return delta;
        }else{
            int ret=0;
            for (int &i=cur[x];i;i=e[i].nxt){
                if (e[i].f>0 && dist[e[i].v]==dist[x]+1){
                    int ddelta=dfs(e[i].v,min(e[i].f,delta));
                    e[i].f-=ddelta;
                    e[i^1].f+=ddelta;
                    delta-=ddelta;
                    ret+=ddelta;
                }
            }
            return ret;
        }
    }
    inline int Max_Flow(int src0,int sink0){
        src=src0;
        sink=sink0;
        int ret=0;
        while(bfs()){
            memcpy(cur,head,sizeof(head));
            ret+=dfs(src,Inf);
        }
        return ret;
    }
};
Dinic dinic;
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    int src=n+m+1,sink=n+m+2;
    dinic.init();
    for (int i=1;i<=m;i++){
        int cst;
        scanf("%d",&cst);
        dinic.addEdge(i,sink,cst);
    }
    int sum=0;
    for (int i=1;i<=n;i++){
        int a,k;
        scanf("%d%d",&a,&k);
        sum+=a;
        dinic.addEdge(src,m+i,a);
        for (int j=1;j<=k;j++){
            int st;
            scanf("%d",&st);
            dinic.addEdge(m+i,st,dinic.Inf);
        }
    }
    printf("%d\n",sum-dinic.Max_Flow(src,sink));
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

//while(true) RP++;

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#define LL long long

using namespace std;

struct Dinic{

const static int Maxn=500;

const static int Maxm=Maxn*Maxn;

const static int Inf=2100000000;

int head[Maxn+5];

int cur[Maxn+5];

struct Edge{

int v,nxt,f;

Edge(){}

Edge(int v0,int n0,int f0){

v=v0;

nxt=n0;

f=f0;

}

};

Edge e[Maxm*2+5];

int nume;

inline void init(){

nume=1;

memset(head,0,sizeof(head));

}

inline void insertEdge(int u,int v,int f){

e[++nume]=Edge(v,head[u],f);

head[u]=nume;

}

inline void addEdge(int u,int v,int f){

insertEdge(u,v,f);

insertEdge(v,u,0);

}

int dist[Maxn+5];

queue<int> que;

int src,sink;

inline bool bfs(){

while(!que.empty())que.pop();

memset(dist,-1,sizeof(dist));

dist[src]=0;

que.push(src);

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=head[now];i;i=e[i].nxt){

if (e[i].f>0 && dist[e[i].v]==-1){

dist[e[i].v]=dist[now]+1;

que.push(e[i].v);

}

return dist[sink]!=-1;

}

int dfs(int x,int delta){

if (x==sink){

return delta;

}else{

int ret=0;

for (int &i=cur[x];i;i=e[i].nxt){

if (e[i].f>0 && dist[e[i].v]==dist[x]+1){

int ddelta=dfs(e[i].v,min(e[i].f,delta));

e[i].f-=ddelta;

e[i^1].f+=ddelta;

delta-=ddelta;

ret+=ddelta;

}

return ret;

}

inline int Max_Flow(int src0,int sink0){

src=src0;

sink=sink0;

int ret=0;

while(bfs()){

memcpy(cur,head,sizeof(head));

ret+=dfs(src,Inf);

}

return ret;

}

};

Dinic dinic;

int n,m;

int main(){

scanf("%d%d",&n,&m);

int src=n+m+1,sink=n+m+2;

dinic.init();

for (int i=1;i<=m;i++){

int cst;

scanf("%d",&cst);

dinic.addEdge(i,sink,cst);

}

int sum=0;

for (int i=1;i<=n;i++){

int a,k;

scanf("%d%d",&a,&k);

sum+=a;

dinic.addEdge(src,m+i,a);

for (int j=1;j<=k;j++){

int st;

scanf("%d",&st);

dinic.addEdge(m+i,st,dinic.Inf);

}

printf("%d\n",sum-dinic.Max_Flow(src,sink));

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑

HihoCoder 119周网络流五·最大权闭合子图

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

HihoCoder 119周 网络流五·最大权闭合子图

题解

代码

扫一扫支付

评论 放弃治疗

HihoCoder 119周网络流五·最大权闭合子图

评论放弃治疗