HDU 4971 （最小割）

Problem A simple brute force problem （HDU 4971）

题目大意

　　有n个项目和m个问题，完成每个项目有对应收入，解决每个问题需要对应花费，给出每个项目需解决的问题以及各问题间的依赖关系，求最大利润。

解题分析

　　最大权闭合子图用来解决一下有依赖关系的问题。

　　X集权值为正，Y集权值为负。X集的某些点依赖于Y集，Y集的某些点互相依赖。

　　从S向X集的每个点连流量为权值的边，y集的每个点向T连流量为权值的边，若两个点互相依赖，则连一条权值为INF的边。

　　求一遍最小割，最后答案为X集总权值减去最小割。

参考程序

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <queue>
  5 using namespace std;
  6 
  7 #define INF 2000000000
  8 #define V 100
  9 #define E 100000
 10 int n,m,ans,dis[V],S,T;
 11 
 12 struct line{
 13     int u,v,c,nt;
 14 }eg[E];
 15 int lt[V],sum=1;
 16 
 17 void adt(int u,int v,int c){
 18     eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c; eg[sum].nt=lt[u]; lt[u]=sum;
 19 }
 20 
 21 void add(int u,int v,int c){
 22     adt(u,v,c); adt(v,u,0);
 23 }
 24 
 25 void init(){
 26     memset(lt,0,sizeof(lt));
 27     sum=1; ans=0;
 28 }
 29 
 30 bool bfs(){
 31     memset(dis,0,sizeof(dis));
 32     dis[S]=1;
 33     queue<int> Q;
 34     Q.push(S);
 35     while (!Q.empty()){
 36         int u=Q.front();
 37         Q.pop();
 38         for (int i=lt[u];i;i=eg[i].nt){
 39             int v=eg[i].v;
 40             if (eg[i].c && !dis[v]){
 41                 dis[v]=dis[u]+1;
 42                 Q.push(v);
 43             }
 44         }
 45     }
 46     return dis[T]>0;
 47 }
 48 
 49 int dfs(int u,int flow){
 50     if (u==T) return flow;
 51     int res=0,f;
 52     for (int i=lt[u];i;i=eg[i].nt){
 53         int v=eg[i].v;
 54         if (eg[i].c&&dis[v]==dis[u]+1){
 55             f=dfs(v,min(flow-res,eg[i].c));
 56             res+=f;
 57             eg[i].c-=f;
 58             eg[i ^ 1].c+=f;
 59             if (flow==res) break;
 60         }
 61     }
 62     if (!res) dis[u]=-1;
 63     return res;
 64 }
 65 
 66 int dinic(){
 67     int sum=0;
 68     while (bfs()) sum+=dfs(S,INF);
 69     return sum;
 70 }
 71 int main(){
 72 
 73     int Tp,cas=0;
 74     scanf("%d",&Tp);
 75     while (Tp--){
 76         init();
 77         scanf("%d %d",&n,&m);
 78         S=0,T=n+m+1;
 79         int x;
 80         for (int i=1;i<=n;i++){
 81             scanf("%d",&x);
 82             add(S,i,x);
 83             ans+=x;
 84         }
 85         for (int i=1;i<=m;i++){
 86             scanf("%d",&x);
 87             add(i+n,T,x);
 88         }
 89         for (int i=1;i<=n;i++){
 90             int num;
 91             scanf("%d",&num);
 92             for (int j=1;j<=num;j++){
 93                 scanf("%d",&x);
 94                 add(i,x+1+n,INF);
 95             }
 96         }
 97         for (int i=1;i<=m;i++)
 98             for (int j=1;j<=m;j++){
 99                 scanf("%d",&x);
100                 if (x) add(i+n,j+n,INF);
101             }
102         n=T;
103         printf("Case #%d: %d
",++cas,ans-dinic());        
104     }
105 }

View Code