网络流最小割 POJ 3469

题意 2个CPU n个任务给出在第一个第二个运行时的花费

m 个 a b 不在同一个CPU运行的额外花费

建图源点 -> n -> 汇点

权 a1 b1

反向边权 0;

还有 a->b 权 w;

不知道为什么b->a 权也是w

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<queue>
  5 
  6 using namespace std;
  7 
  8 int n,m;
  9 int S,T,cnt;
 10 #define inf 100000000
 11 #define MAXN 20000
 12 #define MAXN1 250000
 13 int head[MAXN+10];
 14 int vis[MAXN+10];
 15 
 16 struct edg
 17 {
 18     int to,next,w;
 19 }x[MAXN1*2];
 20 
 21 void add(int u,int v,int w)
 22 {
 23     x[cnt].next=head[u];
 24     x[cnt].to=v;
 25     x[cnt].w=w;
 26     head[u]=cnt++;
 27 }
 28 int bfs()
 29 {
 30     queue<int>q1;
 31     memset(vis,-1,sizeof(vis));
 32     vis[S]=0;
 33     q1.push(S);
 34 
 35     while(!q1.empty())
 36     {
 37         int now=q1.front();
 38         q1.pop();
 39         int j;
 40 
 41         for(j=head[now];j!=-1;j=x[j].next)
 42         {
 43             if(vis[x[j].to]<0&&x[j].w)
 44             {
 45                 vis[x[j].to]=vis[now]+1;
 46                 q1.push(x[j].to);
 47             }
 48         }
 49     }
 50     return vis[T]!=-1;
 51 
 52 }
 53 int dfs(int u,int w)
 54 {
 55     int ans=0;
 56     if(u==T)
 57         return w;
 58     int j;
 59     for(j=head[u];j!=-1;j=x[j].next)
 60     {
 61         if(vis[x[j].to]==vis[u]+1&&x[j].w)
 62         {
 63             int b=dfs(x[j].to,min(w-ans,x[j].w));
 64             x[j].w-=b;
 65             x[j^1].w+=b;
 66             ans+=b;
 67         }
 68     }
 69     return ans;
 70 }
 71 
 72 int main()
 73 {
 74 
 75     while(scanf("%d%d",&n,&m)!=EOF)
 76     {
 77         int i;
 78         memset(head,-1,sizeof(head));
 79         cnt=0;
 80         S=0;
 81         T=n+1;
 82 
 83         for(i=1;i<=n;i++)
 84         {
 85             int a,b;
 86             scanf("%d%d",&a,&b);
 87             add(S,i,a),add(i,S,0);
 88             add(i,T,b),add(T,i,0);
 89         }
 90         for(i=1;i<=m;i++)
 91         {
 92             int a,b,w;
 93             scanf("%d%d%d",&a,&b,&w);
 94             add(a,b,w),add(b,a,w);
 95         }
 96         int ans=0;
 97         while(bfs())
 98             ans+=dfs(S,inf);
 99         printf("%d
",ans);
100     }
101     return 0;
102 }