【网络流】网络流小总结

一、dinic最大流

我的模板。模板上已经有了dfs上的优化（比我以前的快多了。。）优化啊优化。

bool bfs(int st,int ed)
{
    while(!q.empty()) q.pop();
    memset(d,-1,sizeof(d));
    q.push(st);
    d[st]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=first[x];i!=-1;i=a[i].next)
        {
            int y=a[i].y;
            if(d[y]==-1 && a[i].d>0)
            {
                d[y]=d[x]+1;
                q.push(y);
            }
        }    
    }
    return (d[ed]!=-1);
}

int dfs(int x,int flow,int ed)
{
    int k,p,r=0;
    if(x==ed) return flow;
    for(int i=first[x];i!=-1;i=a[i].next)
    {
        int y=a[i].y;
        if(d[y]==d[x]+1 && a[i].d>0)
        {
            p=minn(a[i].d,flow-r);
            p=dfs(y,p,ed);
            r+=p; //优化，把从这个点开始能流的全部流了
            a[i].d-=p;
            a[i^1].d+=p;
        }
                if(r==flow) break; // 优化
    }
    if(!r) d[x]=-1;  //优化
    return r;
}

int dinic(int st,int ed)
{
    int ans=0;
    while(bfs(st,ed))
    {
        int k;
        while(k=dfs(st,INF,ed)) ans+=k;
    }
    return ans;
}

dinic

二、上下界网络流

建立超级源点ss,超级汇点tt(上图中的s改为ss，t改为tt)

对于每条x到y，下界为k1，上界为k2的边(x,y,k1,k2)，拆成如图这种形式：(x,y,k2-k1)（自由流），（ss,y,k1）（必须流入），(x,tt,k1)（必须流出）。

（1）没有源点和汇点：

可行流：跑一遍最大流，看是否满流。满流则有可行流。

最大流：每条边加一个费用f=1，然后跑最大费用循环流（详见下面）。

最小流：每条边加一个费用f=1，然后跑最小费用循环流。

（2）有源点和汇点：

原来的源点s，原来的汇点t。在s和t之间建边(t,s,INF)，使原图变为无源汇的循环流。

可行流：拆边后跑一遍最大流，满流则有可行流。

最大流：去掉ss、tt（去掉后无论怎么跑都是已经满足了下界的可行流），然后从原来的源汇点s到t跑一遍最大流，让残余网络的增广路全部加上去。此时(s,t,INF)的那条边的反向边（t,s）的流量就是答案。

最小路：去掉ss、tt后，从原来的源汇点t到s跑一遍最大流（逆向求解，让最多的流量还回去）。

上下界网络路讲解：http://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html

模板（poj2396）

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 #include<vector>
  7 using namespace std;
  8 
  9 const int N=500,M=500,INF=(int)1e9;
 10 const int S=N+M+4;
 11 int n,m,s,t,ss,tt,len,sum,bk;
 12 int d[N+M+4],p[N][M],first[N+M+4],map[2][N][M];
 13 struct node{int x,y,d,next;}a[N*M*2];
 14 queue<int> q;
 15 
 16 int minn(int x,int y){return x<y ? x:y;}
 17 int maxx(int x,int y){return x>y ? x:y;}
 18 
 19 void ins(int x,int y,int d)
 20 {
 21     a[++len].x=x;a[len].y=y;a[len].d=d;
 22     a[len].next=first[x];first[x]=len;
 23     if(x==ss) sum+=d;
 24     swap(x,y);
 25     a[++len].x=x;a[len].y=y;a[len].d=0;
 26     a[len].next=first[x];first[x]=len;
 27 }
 28 
 29 void make_edge(int x,int y)
 30 {
 31     if(map[0][x][y]>map[1][x][y]) bk=0;
 32     if(map[0][x][y]==0) ins(x,y,map[1][x][y]);
 33     else
 34     {
 35         ins(ss,y,map[0][x][y]);
 36         ins(x,tt,map[0][x][y]);
 37         ins(x,y,map[1][x][y]-map[0][x][y]);
 38     }
 39 }
 40 
 41 void build(char c,int x,int y,int z)
 42 {
 43     int t1=0,t2=INF;
 44     if(c=='=') t1=t2=z;
 45     if(c=='>') t1=z+1;
 46     if(c=='<') t2=z-1;
 47     map[0][x][y]=maxx(map[0][x][y],t1);
 48     map[1][x][y]=minn(map[1][x][y],t2);
 49     
 50 }
 51 
 52 bool bfs(int st,int ed)
 53 {
 54     while(!q.empty()) q.pop();
 55     memset(d,-1,sizeof(d));
 56     q.push(st);
 57     d[st]=0;
 58     while(!q.empty())
 59     {
 60         int x=q.front();q.pop();
 61         for(int i=first[x];i!=-1;i=a[i].next)
 62         {
 63             int y=a[i].y;
 64             if(d[y]==-1 && a[i].d>0)
 65             {
 66                 d[y]=d[x]+1;
 67                 q.push(y);
 68             }
 69         }    
 70     }
 71     return (d[ed]!=-1);
 72 }
 73 
 74 int dfs(int x,int flow,int ed)
 75 {
 76     int k,p,r=0;
 77     if(x==ed) return flow;
 78     for(int i=first[x];i!=-1;i=a[i].next)
 79     {
 80         int y=a[i].y;
 81         if(d[y]==d[x]+1 && a[i].d>0)
 82         {
 83             p=minn(a[i].d,flow-r);
 84             p=dfs(y,p,ed);
 85             r+=p;
 86             a[i].d-=p;
 87             a[i^1].d+=p;
 88         }
 89     }
 90     if(!r) d[x]=-1;
 91     return r;
 92 }
 93 
 94 int dinic(int st,int ed)
 95 {
 96     int ans=0;
 97     while(bfs(st,ed))
 98     {
 99         int k;
100         while(k=dfs(st,INF,ed)) ans+=k;
101     }
102     return ans;
103 }
104 
105 int main()
106 {
107     freopen("a.in","r",stdin);
108     freopen("a.out","w",stdout);
109     int T;
110     scanf("%d",&T);
111     while(T--)
112     {
113         scanf("%d%d",&n,&m);
114         int x,y,z,k;
115         char c;
116         s=n+m+1;t=s+1;ss=t+1;tt=ss+1;
117         len=-1;sum=0;bk=1;
118         memset(first,-1,sizeof(first));
119         memset(map[0],0,sizeof(map[0]));
120         memset(map[1],63,sizeof(map[1]));
121         memset(p,0,sizeof(p));
122         int sum1=0,sum2=0;
123         for(int i=1;i<=n;i++)
124         {
125             scanf("%d",&x);
126             map[0][s][i]=map[1][s][i]=x;
127             make_edge(s,i);
128             sum1+=x;
129         }
130         for(int i=n+1;i<=n+m;i++)
131         {
132             scanf("%d",&x);
133             map[0][i][t]=map[1][i][t]=x;
134             make_edge(i,t);
135             sum2+=x;
136         }
137         if(sum1!=sum2) bk=0;
138         scanf("%d",&k);
139         for(int i=1;i<=k;i++)
140         {
141             scanf("%d%d",&x,&y);getchar();
142             scanf("%c%d",&c,&z);
143             if(x && y) build(c,x,y+n,z);
144             if(!x && y)
145                 for(int j=1;j<=n;j++)
146                     build(c,j,y+n,z);
147             if(x && !y)
148                 for(int j=1;j<=m;j++)
149                     build(c,x,j+n,z);
150             if(!x && !y)
151                 for(int j=1;j<=n;j++)
152                     for(int l=1;l<=m;l++)
153                         build(c,j,l+n,z);
154         }
155         for(int i=1;i<=n;i++)
156             for(int j=n+1;j<=n+m;j++)
157                 make_edge(i,j);
158         ins(t,s,INF);
159         if(!bk || dinic(ss,tt)!=sum) printf("IMPOSSIBLE
");
160         else 
161         {
162             for(int i=0;i<len;i++)
163             {
164                 x=a[i].x;y=a[i].y;
165                 if(x<=n+m && y<=n+m)
166                 {
167                     if(!p[x][y-n]) p[x][y-n]=map[0][x][y]+a[i^1].d;
168                 }
169             }
170             for(int i=1;i<=n;i++)
171             {
172                 for(int j=1;j<=m;j++)                    
173                     printf("%d ",p[i][j]);
174                 printf("
");
175             }
176         }
177         printf("
");
178     }
179     return 0;
180 }

poj2396

三、最小费用最大流

在满足最大流的前提下求最小费用，就是在bfs的时候找一条费用最小的增广路。

 1 void ins(int x,int y,int d,int f)
 2 {
 3     a[++len].x=x;a[len].y=y;a[len].d=d;a[len].f=f;
 4     a[len].next=first[x];first[x]=len;
 5     a[++len].x=y;a[len].y=x;a[len].d=0;a[len].f=-f;
 6     a[len].next=first[y];first[y]=len;
 7 }
 8 
 9 int bfs(int st,int ed)
10 {
11     while(!q.empty()) q.pop();
12     memset(pre,-1,sizeof(pre));
13     memset(dis,63,sizeof(dis));
14     memset(in,0,sizeof(in));
15     memset(flow,0,sizeof(flow));
16     pre[st]=0;dis[st]=0;in[st]=1;flow[st]=INF;q.push(st);
17     while(!q.empty())
18     {
19         int x=q.front();in[x]=0;q.pop();
20         for(int i=first[x];i!=-1;i=a[i].next)
21         {
22             int y=a[i].y;
23             if(a[i].d && dis[y]>dis[x]+a[i].f)
24             {
25                 dis[y]=dis[x]+a[i].f;
26                 pre[y]=i;
27                 flow[y]=minn(a[i].d,flow[x]);
28                 if(!in[y]) {in[y]=1;q.push(y);}
29             }
30         }
31     }
32     if(pre[ed]==-1) return -1;
33     return flow[ed];
34 }
35 
36 void MFMC(int st,int ed)//max flow min cost
37 {
38     int k,p;
39     fl=0,cl=0;
40     while((k=bfs(st,ed))!=-1)
41     {
42         fl+=k;
43         cl+=dis[ed]*k;
44         p=ed;
45         while(p!=st)
46         {
47             a[pre[p]].d-=k;
48             a[pre[p]^1].d+=k;
49             p=a[pre[p]].x;
50         }
51     }
52 }

费用流

四、最小割

根据最大流最小割原理，最大流就是最小割。主要是建图模型。

经典例题：一些资源，要不给A，要不给B，有相应的收益，问最大收益。写在我的题表里了。

我写了题解：http://www.cnblogs.com/KonjakJuruo/p/5516479.html

五、最大费用循环流

每条边有上下界k1、k2，费用f。问最大费用循环流。

对于每条边(x,y,k1,k2,f)，拆成：

1.(x,y,k1,k1,f) (再按上下界拆边，即(s,y,k1,f) (x,t,k1,f)), （x到y之间一定要流k1的流量）

2.(y,x,k2-k1,-f) , (s,y,k2-k1,0) , (x,t,k2-f1,f)；（x到y之间有k2-k1的自由流，先假设全部都可以得到，然后建（y,x,k2-k1,-f）就是给它反悔的机会，如果必须反悔就减回f*流量）

跑最大流，用k2的和判满流，满流则有解。

重点来了，题表及代码：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 #include<vector>
  7 using namespace std;
  8 
  9 const int N=500,M=500,INF=(int)1e9;
 10 const int S=N+M+4;
 11 int n,m,s,t,ss,tt,len,sum,bk;
 12 int d[N+M+4],p[N][M],first[N+M+4],map[2][N][M];
 13 struct node{int x,y,d,next;}a[N*M*2];
 14 queue<int> q;
 15 
 16 int minn(int x,int y){return x<y ? x:y;}
 17 int maxx(int x,int y){return x>y ? x:y;}
 18 
 19 void ins(int x,int y,int d)
 20 {
 21     a[++len].x=x;a[len].y=y;a[len].d=d;
 22     a[len].next=first[x];first[x]=len;
 23     if(x==ss) sum+=d;
 24     swap(x,y);
 25     a[++len].x=x;a[len].y=y;a[len].d=0;
 26     a[len].next=first[x];first[x]=len;
 27 }
 28 
 29 void make_edge(int x,int y)
 30 {
 31     if(map[0][x][y]>map[1][x][y]) bk=0;
 32     if(map[0][x][y]==0) ins(x,y,map[1][x][y]);
 33     else
 34     {
 35         ins(ss,y,map[0][x][y]);
 36         ins(x,tt,map[0][x][y]);
 37         ins(x,y,map[1][x][y]-map[0][x][y]);
 38     }
 39 }
 40 
 41 void build(char c,int x,int y,int z)
 42 {
 43     int t1=0,t2=INF;
 44     if(c=='=') t1=t2=z;
 45     if(c=='>') t1=z+1;
 46     if(c=='<') t2=z-1;
 47     map[0][x][y]=maxx(map[0][x][y],t1);
 48     map[1][x][y]=minn(map[1][x][y],t2);
 49     
 50 }
 51 
 52 bool bfs(int st,int ed)
 53 {
 54     while(!q.empty()) q.pop();
 55     memset(d,-1,sizeof(d));
 56     q.push(st);
 57     d[st]=0;
 58     while(!q.empty())
 59     {
 60         int x=q.front();q.pop();
 61         for(int i=first[x];i!=-1;i=a[i].next)
 62         {
 63             int y=a[i].y;
 64             if(d[y]==-1 && a[i].d>0)
 65             {
 66                 d[y]=d[x]+1;
 67                 q.push(y);
 68             }
 69         }    
 70     }
 71     return (d[ed]!=-1);
 72 }
 73 
 74 int dfs(int x,int flow,int ed)
 75 {
 76     int k,p,r=0;
 77     if(x==ed) return flow;
 78     for(int i=first[x];i!=-1;i=a[i].next)
 79     {
 80         int y=a[i].y;
 81         if(d[y]==d[x]+1 && a[i].d>0)
 82         {
 83             p=minn(a[i].d,flow-r);
 84             p=dfs(y,p,ed);
 85             r+=p;
 86             a[i].d-=p;
 87             a[i^1].d+=p;
 88         }
 89     }
 90     if(!r) d[x]=-1;
 91     return r;
 92 }
 93 
 94 int dinic(int st,int ed)
 95 {
 96     int ans=0;
 97     while(bfs(st,ed))
 98     {
 99         int k;
100         while(k=dfs(st,INF,ed)) ans+=k;
101     }
102     return ans;
103 }
104 
105 int main()
106 {
107     int T;
108     scanf("%d",&T);
109     while(T--)
110     {
111         scanf("%d%d",&n,&m);
112         int x,y,z,k;
113         char c;
114         s=n+m+1;t=s+1;ss=t+1;tt=ss+1;
115         len=-1;sum=0;bk=1;
116         memset(first,-1,sizeof(first));
117         memset(map[0],0,sizeof(map[0]));
118         memset(map[1],63,sizeof(map[1]));
119         memset(p,0,sizeof(p));
120         int sum1=0,sum2=0;
121         for(int i=1;i<=n;i++)
122         {
123             scanf("%d",&x);
124             map[0][s][i]=map[1][s][i]=x;
125             make_edge(s,i);
126             sum1+=x;
127         }
128         for(int i=n+1;i<=n+m;i++)
129         {
130             scanf("%d",&x);
131             map[0][i][t]=map[1][i][t]=x;
132             make_edge(i,t);
133             sum2+=x;
134         }
135         if(sum1!=sum2) bk=0;
136         scanf("%d",&k);
137         for(int i=1;i<=k;i++)
138         {
139             scanf("%d%d",&x,&y);getchar();
140             scanf("%c%d",&c,&z);
141             if(x && y) build(c,x,y+n,z);
142             if(!x && y)
143                 for(int j=1;j<=n;j++)
144                     build(c,j,y+n,z);
145             if(x && !y)
146                 for(int j=1;j<=m;j++)
147                     build(c,x,j+n,z);
148             if(!x && !y)
149                 for(int j=1;j<=n;j++)
150                     for(int l=1;l<=m;l++)
151                         build(c,j,l+n,z);
152         }
153         for(int i=1;i<=n;i++)
154             for(int j=n+1;j<=n+m;j++)
155                 make_edge(i,j);
156         ins(t,s,INF);
157         if(!bk || dinic(ss,tt)!=sum) printf("IMPOSSIBLE
");
158         else 
159         {
160             for(int i=0;i<len;i++)
161             {
162                 x=a[i].x;y=a[i].y;
163                 if(x<=n+m && y<=n+m)
164                 {
165                     if(!p[x][y-n]) p[x][y-n]=map[0][x][y]+a[i^1].d;
166                 }
167             }
168             for(int i=1;i<=n;i++)
169             {
170                 for(int j=1;j<=m;j++)                    
171                     printf("%d ",p[i][j]);
172                 printf("
");
173             }
174         }
175         printf("
");
176     }
177     return 0;
178 }

poj2396

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

const int N=1100,M=5100,K=110,INF=(int)1e9;
int s,t,len,fl,cl,pre[N],dis[N],flow[N],first[N];
bool in[N];
struct node{
    int x,y,d,f,next;
}a[51000];
queue<int> q;

int minn(int x,int y){return x<y ? x:y;}

void ins(int x,int y,int d,int f)
{
    a[++len].x=x;a[len].y=y;a[len].d=d;a[len].f=f;
    a[len].next=first[x];first[x]=len;
    a[++len].x=y;a[len].y=x;a[len].d=0;a[len].f=-f;
    a[len].next=first[y];first[y]=len;
}

int bfs(int st,int ed)
{
    while(!q.empty()) q.pop();
    memset(pre,-1,sizeof(pre));
    memset(dis,63,sizeof(dis));
    memset(in,0,sizeof(in));
    memset(flow,0,sizeof(flow));
    pre[st]=0;dis[st]=0;in[st]=1;flow[st]=INF;q.push(st);
    while(!q.empty())
    {
        int x=q.front();in[x]=0;q.pop();
        for(int i=first[x];i!=-1;i=a[i].next)
        {
            int y=a[i].y;
            if(a[i].d && dis[y]>dis[x]+a[i].f)
            {
                dis[y]=dis[x]+a[i].f;
                pre[y]=i;
                flow[y]=minn(a[i].d,flow[x]);
                if(!in[y]) {in[y]=1;q.push(y);}
            }
        }
    }
    if(pre[ed]==-1) return -1;
    return flow[ed];
}

void MFMC(int st,int ed)//max flow min cost
{
    int k,p;
    fl=0,cl=0;
    while((k=bfs(st,ed))!=-1)
    {
        fl+=k;
        cl+=dis[ed]*k;
        p=ed;
        while(p!=st)
        {
            a[pre[p]].d-=k;
            a[pre[p]^1].d+=k;
            p=a[pre[p]].x;
        }
    }
}

int main()
{
    int n,m,kk;
    while(scanf("%d%d%d",&n,&m,&kk)!=EOF)
    {
        int x,y,d,f;
        len=-1;
        memset(first,-1,sizeof(first));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&x,&y,&f,&d);
            for(int j=1;j<=d;j++)
                ins(x,y,1,f*(2*j-1));
        }
        s=n+1,t=n;
        ins(s,1,kk,0);
        MFMC(s,t);
        // printf("fl = %d  cl = %d
",fl,cl);
        if(fl==kk) printf("%d
",cl);
        else printf("-1
");
    }
    return 0;
}

LA5095

  1 // 方法一 把每个询问看成一个点，然后A的询问连源点，B的询问连汇点，如果AB间的某个
  2 // 询问有矛盾就在它们中间连一条无限大的边，ans=sum-最小割。
  3 
  4 #include<cstdio>
  5 #include<cstdlib>
  6 #include<cstring>
  7 #include<iostream>
  8 #include<queue>
  9 #include<vector>
 10 using namespace std;
 11 
 12 const int N=300100,INF=(int)1e9;
 13 int s,t,len,num;
 14 int first[2*N],dis[2*N];
 15 int A[N],B[N],p1[N],p2[N];
 16 // bool vis[2*N];
 17 bool vis[3100][3100];
 18 struct node{
 19     int x,y,d,next;
 20 }a[6*N];
 21 queue<int> q;
 22 
 23 int minn(int x,int y){return x<y ? x:y;}
 24 int maxx(int x,int y){return x>y ? x:y;}
 25 
 26 void ins(int x,int y,int d)
 27 {
 28     a[++len].x=x;a[len].y=y;a[len].d=d;
 29     a[len].next=first[x];first[x]=len;
 30     a[++len].x=y;a[len].y=x;a[len].d=0;
 31     a[len].next=first[y];first[y]=len;
 32 }
 33 
 34 bool bfs(int st,int ed)
 35 {
 36     while(!q.empty()) q.pop();
 37     memset(dis,-1,sizeof(dis));
 38     dis[st]=0;
 39     q.push(st);
 40     while(!q.empty())
 41     {
 42         int x=q.front();q.pop();
 43         for(int i=first[x];i!=-1;i=a[i].next)
 44         {
 45             int y=a[i].y;
 46             if(dis[y]==-1 && a[i].d>0)
 47             {
 48                 dis[y]=dis[x]+1;
 49                 q.push(y);
 50             }
 51         }
 52     }
 53     return (dis[ed]!=-1);
 54 }
 55 
 56 int dfs(int x,int ed,int flow)
 57 {
 58     int r=0,p;
 59     if(x==ed) return flow;
 60     for(int i=first[x];i!=-1;i=a[i].next)
 61     {
 62         int y=a[i].y;
 63         if(dis[y]==dis[x]+1 && a[i].d>0)
 64         {
 65             p=minn(a[i].d,flow-r);
 66             p=dfs(y,ed,p);
 67             r+=p;
 68             a[i].d-=p;
 69             a[i^1].d+=p;
 70         }
 71     }
 72     if(!r) dis[x]=-1;
 73     return r;
 74 }
 75 
 76 int dinic(int st,int ed)
 77 {
 78     int ans=0;
 79     while(bfs(st,ed))
 80     {
 81         int p;
 82         while(p=dfs(st,ed,INF)) ans+=p;
 83     }
 84     return ans;
 85 }
 86 
 87 int main()
 88 {
 89     int T,cas=0;
 90     scanf("%d",&T);
 91     while(T--)
 92     {
 93         len=-1;
 94         memset(first,-1,sizeof(first));
 95         memset(A,0,sizeof(A));
 96         memset(B,0,sizeof(B));
 97         memset(vis,0,sizeof(vis));
 98         int n,m,sum=0,mx=0,num=300001;
 99         scanf("%d",&n);
100         for(int i=1;i<=n;i++)
101         {
102             scanf("%d",&p1[i]);
103             sum+=p1[i];
104             int x;num++;
105             while(1)
106             {
107                 char c;
108                 scanf("%d%c",&x,&c);
109                 A[x]=i;
110                 mx=maxx(mx,x);
111                 if(c=='
') break;
112             }
113         }
114         scanf("%d",&m);
115         s=0,t=n+m+1;
116         for(int i=1;i<=m;i++)
117         {
118             scanf("%d",&p2[i]);
119             sum+=p2[i];num++;
120             int x;
121             while(1)
122             {
123                 char c;
124                 scanf("%d%c",&x,&c);
125                 B[x]=i;
126                 mx=maxx(mx,x);
127                 if(c=='
') break;
128             }
129         }
130         for(int i=1;i<=n;i++) ins(s,i,p1[i]);
131         for(int i=1;i<=m;i++) ins(i+n,t,p2[i]);
132         for(int i=1;i<=mx;i++)
133         {
134             if(!A[i]||!B[i]||vis[A[i]][B[i]]) continue;
135             vis[A[i]][B[i]]=true;
136             ins(A[i],B[i]+n,INF);
137         }
138         printf("Case %d:
",++cas);
139         printf("%d
",sum-dinic(s,t));
140         if(T) printf("
");
141     }
142     return 0;
143 }

LA3487-方法一

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 #include<vector>
  7 using namespace std;
  8 
  9 const int N=300100,INF=(int)1e9;
 10 int s,t,len,num;
 11 int first[2*N],dis[2*N];
 12 int A[N],B[N];
 13 bool vis[3100][3100];
 14 struct node{
 15     int x,y,d,next;
 16 }a[6*N];
 17 queue<int> q;
 18 
 19 int minn(int x,int y){return x<y ? x:y;}
 20 int maxx(int x,int y){return x>y ? x:y;}
 21 
 22 void ins(int x,int y,int d)
 23 {
 24     a[++len].x=x;a[len].y=y;a[len].d=d;
 25     a[len].next=first[x];first[x]=len;
 26     a[++len].x=y;a[len].y=x;a[len].d=0;
 27     a[len].next=first[y];first[y]=len;
 28 }
 29 
 30 bool bfs(int st,int ed)
 31 {
 32     while(!q.empty()) q.pop();
 33     memset(dis,-1,sizeof(dis));
 34     dis[st]=0;
 35     q.push(st);
 36     while(!q.empty())
 37     {
 38         int x=q.front();q.pop();
 39         for(int i=first[x];i!=-1;i=a[i].next)
 40         {
 41             int y=a[i].y;
 42             if(dis[y]==-1 && a[i].d>0)
 43             {
 44                 dis[y]=dis[x]+1;
 45                 q.push(y);
 46             }
 47         }
 48     }
 49     return (dis[ed]!=-1);
 50 }
 51 
 52 int dfs(int x,int ed,int flow)
 53 {
 54     int r=0,p;
 55     if(x==ed) return flow;
 56     for(int i=first[x];i!=-1;i=a[i].next)
 57     {
 58         int y=a[i].y;
 59         if(dis[y]==dis[x]+1 && a[i].d>0)
 60         {
 61             p=minn(a[i].d,flow-r);
 62             p=dfs(y,ed,p);
 63             r+=p;
 64             a[i].d-=p;
 65             a[i^1].d+=p;
 66         }
 67     }
 68     if(!r) dis[x]=-1;
 69     return r;
 70 }
 71 
 72 int dinic(int st,int ed)
 73 {
 74     int ans=0;
 75     while(bfs(st,ed))
 76     {
 77         int p;
 78         while(p=dfs(st,ed,INF)) ans+=p;
 79     }
 80     return ans;
 81 }
 82 
 83 int main()
 84 {
 85     int T,cas=0;
 86     scanf("%d",&T);
 87     while(T--)
 88     {
 89         len=-1;
 90         memset(first,-1,sizeof(first));
 91         memset(A,0,sizeof(A));
 92         memset(B,0,sizeof(B));
 93         memset(vis,0,sizeof(vis));
 94         int n,m,p,sum=0,mx=0,num=300001;
 95         scanf("%d",&n);
 96         for(int i=1;i<=n;i++)
 97         {
 98             scanf("%d",&p);
 99             sum+=p;
100             int x;num++;
101             ins(0,num,p);
102             while(1)
103             {
104                 char c;
105                 scanf("%d%c",&x,&c);
106                 ins(num,x+1,INF);
107                 if(c=='
') break;
108             }
109         }
110         scanf("%d",&m);
111         s=0,t=1;
112         for(int i=1;i<=m;i++)
113         {
114             scanf("%d",&p);
115             sum+=p;num++;
116             ins(num,t,p);
117             int x;
118             while(1)
119             {
120                 char c;
121                 scanf("%d%c",&x,&c);
122                 ins(x+1,num,INF);
123                 if(c=='
') break;
124             }
125         }
126         // for(int i=1;i<=n;i++) ins(s,i,p1[i]);
127         // for(int i=1;i<=m;i++) ins(i+n,t,p2[i]);
128         for(int i=1;i<=mx;i++)
129         {
130             if(!A[i]||!B[i]||vis[A[i]][B[i]]) continue;
131             vis[A[i]][B[i]]=true;
132             ins(A[i],B[i]+n,INF);
133         }
134         printf("Case %d:
",++cas);
135         printf("%d
",sum-dinic(s,t));
136         if(T) printf("
");
137     }
138     return 0;
139 }

LA3487-方法二

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;

const int N=50*2,INF=(int)1e9;
char ss[N][N];
int s,t,n,A,B,fl,cl,len,must_have,first[N],flow[N],dis[N],pre[N],s1[N],s2[N];
bool in[N];
struct node{
    int x,y,d,f,next;
}a[2*N*N];
queue<int> q;
int minn(int x,int y){return x<y ? x:y;}
int maxx(int x,int y){return x>y ? x:y;}

void ins(int x,int y,int d,int f)
{
    a[++len].x=x;a[len].y=y;a[len].d=d;a[len].f=f;
    a[len].next=first[x];first[x]=len;
    a[++len].x=y;a[len].y=x;a[len].d=0;a[len].f=-f;
    a[len].next=first[y];first[y]=len;
}

int bfs(int st,int ed)
{
    while(!q.empty()) q.pop();
    memset(dis,63,sizeof(dis));
    memset(flow,0,sizeof(flow));
    memset(in,0,sizeof(in));
    memset(pre,-1,sizeof(pre));
    q.push(st);
    in[st]=1;dis[st]=0;flow[st]=INF;pre[st]=0;
    while(!q.empty())
    {
        int x=q.front();in[x]=0;q.pop();
        for(int i=first[x];i!=-1;i=a[i].next)
        {
            int y=a[i].y;
            if(a[i].d>0 && dis[y]>dis[x]+a[i].f)
            {
                dis[y]=dis[x]+a[i].f;
                pre[y]=i;
                flow[y]=minn(flow[x],a[i].d);
                if(!in[y]) in[y]=1,q.push(y);
            }
        }
    }
    if(pre[ed]==-1) return 0;
    return flow[ed];
}

void dinic(int st,int ed)
{
    int k;
    fl=0,cl=0;
    while(k=bfs(st,ed))
    {
        fl+=k;
        cl+=dis[ed]*k;
        int p=ed;
        while(p!=st)
        {
            a[pre[p]].d-=k;
            a[pre[p]^1].d+=k;
            p=a[pre[p]].x;
        }
    }
}

bool check()//如果答案是0
{
    int mx=0;
    memset(s1,0,sizeof(s1));
    memset(s2,0,sizeof(s2));
    for(int i=1;i<=n;i++)
        for(int j=0;j<n;j++)
            if(ss[i][j]=='C') must_have++,s1[i]++,s2[j+1]++,mx=maxx(mx,maxx(s1[i],s2[j+1]));  
    for(int i=1;i<=n;i++) if(s1[i]!=s2[i]) return 0;
    if(must_have*A<mx*B) return 0; 
    return 1;
}

int main()
{
    int T=0;
    while(1)
    {
        scanf("%d%d%d",&n,&A,&B);
        if(!n && !A && !B) return 0;
        s=0,t=2*n+1;must_have=0;
        for(int i=1;i<=n;i++)
            scanf("%s",ss[i]);
        int mx,sum,bk=0;
        int ans=-1;
        if(check()) bk=1,ans=must_have;
        for(int k=n;k>=1;k--)
        {
            mx=0,sum=0;
            len=-1;
            memset(first,-1,sizeof(first));
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    int x=i,y=j+1+n;
                    if(ss[i][j]=='.') ins(x,y,1,0);            
                    if(ss[i][j]=='C')
                    {
                        sum++;
                        ins(s,y,1,0);
                        ins(x,t,1,0);                    
                    }
                }
            }
            for(int i=1;i<=n;i++)
            {
                int x=i+n,y=i;
                ins(y,x,k,1);sum+=k;mx+=k;
                ins(s,y,k,0),ins(x,t,k,0);
            }
            dinic(s,t);
            mx-=cl;
            if(sum>fl) continue;
            if(mx && mx*A<k*B) continue;
            bk=1;ans=maxx(ans,mx);
        }
        printf("Case %d: ",++T);
        if(!bk) printf("impossible
");
        else printf("%d
",ans-must_have);
    }
    return 0;
}

LA5131

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<queue>
 6 using namespace std;
 7 
 8 const int N=400,INF=(int)1e9;
 9 int s,t,n,len,fl,cl,first[N],dis[N],pre[N],flow[N];
10 bool in[N];
11 struct node{
12     int x,y,d,f,next;
13 }a[N*N];
14 queue<int> q;
15 
16 int minn(int x,int y){return x<y ? x:y;}
17 
18 void ins(int x,int y,int d,int f)
19 {
20     a[++len].x=x;a[len].y=y;a[len].d=d;a[len].f=f;
21     a[len].next=first[x];first[x]=len;
22     a[++len].y=x;a[len].x=y;a[len].d=0;a[len].f=-f;
23     a[len].next=first[y];first[y]=len;
24 }
25 
26 bool bfs(int st,int ed)
27 {
28     while(!q.empty()) q.pop();
29     memset(dis,-1,sizeof(dis));
30     memset(flow,0,sizeof(flow));
31     memset(pre,-1,sizeof(pre));
32     memset(in,0,sizeof(in));
33     q.push(st);
34     in[st]=1,dis[st]=0,flow[st]=INF;
35     while(!q.empty())
36     {
37         int x=q.front();in[x]=0;q.pop();
38         for(int i=first[x];i!=-1;i=a[i].next)
39         {
40             int y=a[i].y;
41             if(a[i].d && dis[y]<dis[x]+a[i].f)
42             {
43                 dis[y]=dis[x]+a[i].f;
44                 flow[y]=minn(a[i].d,flow[x]);
45                 pre[y]=i;
46                 if(!in[y]) in[y]=1,q.push(y);
47             }
48         }
49     }
50     return flow[ed];
51 }
52 
53 void MCML(int st,int ed)
54 {
55     int k;
56     fl=0;cl=0;
57     while(k=bfs(st,ed))
58     {
59         cl+=dis[ed]*k;
60         fl+=k;
61         int p=ed;
62         while(p!=st)
63         {
64             a[pre[p]].d-=k;
65             a[pre[p]^1].d+=k;
66             p=a[pre[p]].x;
67         }
68     }
69 }
70 
71 int main()
72 {
73     while(1)
74     {
75         scanf("%d",&n);
76         if(!n) return 0;
77         len=-1;
78         memset(first,-1,sizeof(first));
79         s=0,t=366;
80         for(int i=1;i<365;i++) ins(i,i+1,2,0);
81         ins(s,1,2,0);ins(365,t,2,0);
82         for(int i=1;i<=n;i++)
83         {
84             int x,y,d;
85             scanf("%d%d%d",&x,&y,&d);
86             if(x>y) swap(x,y);
87             ins(x,y+1,1,d);
88         }
89         MCML(s,t);
90         printf("%d
",cl);
91     }
92     return 0;
93 }

LA2796

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 using namespace std;
  7 
  8 const int N=3000,INF=(int)1e9;
  9 char ss[N];
 10 int n,m,s,t,len,ct,dis[N],first[N];
 11 bool in[N];
 12 struct node{
 13     int x,y,d,next;
 14 }a[100100];
 15 queue<int> q;
 16 
 17 int idx(int x,int y){return (x-1)*m+y;}
 18 int minn(int x,int y){return x<y ? x:y;}
 19 
 20 void ins(int x,int y,int d)
 21 {
 22     a[++len].x=x;a[len].y=y;a[len].d=d;
 23     a[len].next=first[x];first[x]=len;
 24     a[++len].y=x;a[len].x=y;a[len].d=0;
 25     a[len].next=first[y];first[y]=len;
 26 }
 27 
 28 bool bfs(int st,int ed)
 29 {
 30     while(!q.empty()) q.pop();
 31     memset(dis,-1,sizeof(dis));
 32     memset(in,0,sizeof(in));
 33     q.push(st);dis[st]=0;in[st]=1;
 34     while(!q.empty())
 35     {
 36         int x=q.front();in[x]=0;q.pop();
 37         for(int i=first[x];i!=-1;i=a[i].next)
 38         {
 39             int y=a[i].y;
 40             if(a[i].d && dis[y]==-1)
 41             {
 42                 dis[y]=dis[x]+1;
 43                 if(!in[y]) in[y]=1,q.push(y);
 44             }
 45         }
 46     }
 47     return (dis[ed]!=-1);
 48 }
 49 
 50 int dfs(int x,int ed,int flow)
 51 {
 52     int r=0;
 53     if(x==ed) return flow;
 54     for(int i=first[x];i!=-1;i=a[i].next)
 55     {
 56         int y=a[i].y;
 57         if(a[i].d && dis[y]==dis[x]+1)
 58         {
 59             int p=minn(a[i].d,flow-r);
 60             p=dfs(y,ed,p);
 61             r+=p;
 62             a[i].d-=p;
 63             a[i^1].d+=p;
 64         }
 65         if(r==flow) break;
 66     }
 67     if(!r) dis[x]=-1;
 68     return r;
 69 }
 70 
 71 int dinic(int st,int ed)
 72 {
 73     int k,ans=0;
 74     while(bfs(st,ed))
 75         ans+=dfs(st,ed,INF);
 76     return ans;
 77 }
 78 
 79 int main()
 80 {
 81     int T;
 82     scanf("%d",&T);
 83     while(T--)
 84     {
 85         int d,f,b;
 86         scanf("%d%d",&m,&n);
 87         s=0,t=n*m+1;ct=0;
 88         scanf("%d%d%d",&d,&f,&b);
 89         len=-1;
 90         memset(first,-1,sizeof(first));
 91         for(int i=1;i<=n;i++)
 92         {
 93             scanf("%s",ss+1);
 94             for(int j=1;j<=m;j++)
 95             {    
 96                 int x=idx(i,j),y1=idx(i-1,j),y2=idx(i,j-1);                
 97                 if(ss[j]=='.' && (i==1 || i==n || j==1 || j==m)) 
 98                     ct+=f,ss[j]='#';
 99                 if(ss[j]=='.')
100                 {
101                     ins(s,x,f);ins(x,t,0);
102                     if(i-1>=1) ins(x,y1,b),ins(y1,x,b);    
103                     if(j-1>=1) ins(x,y2,b),ins(y2,x,b);    
104                 }
105                 if(ss[j]=='#')
106                 {
107                     ins(s,x,0);
108                     if(i==1 || i==n || j==1 || j==m) ins(x,t,INF);
109                     else ins(x,t,d);
110                     if(i-1>=1) ins(x,y1,b),ins(y1,x,b);
111                     if(j-1>=1) ins(x,y2,b),ins(y2,x,b);
112                 }
113             }
114         }
115         printf("%d
",ct+dinic(s,t));
116     }
117     return 0;
118 }

uva1515

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;

const int N=110,INF=(int)1e9;
int s,t,sum,fl,cl,len,first[N],pre[N],flow[N],dis[N];
bool bk,in[N];
struct node {
    int x,y,d,f,next;
}a[100010];
queue<int> q;

int minn(int x,int y){return x<y ? x:y;}
int A(int x){return x*2-1;}
int B(int x){return x*2;}

void ins(int x,int y,int d,int f)
{
    a[++len].x=x;a[len].y=y;a[len].d=d;a[len].f=f;
    a[len].next=first[x];first[x]=len;
    a[++len].y=x;a[len].x=y;a[len].d=0;a[len].f=-f;
    a[len].next=first[y];first[y]=len;
}

void addedge(int x,int y,int k1,int k2,int f)
{
    sum+=k2;
    //(x,y,k1,k1,f);
    if(k1)
    {
        ins(s,y,k1,f);
        ins(x,t,k1,f);    
    }
    //(x,y,0,k2-k1,f);
    if(k2!=k1)
    {
        ins(s,y,k2-k1,0);
        ins(y,x,k2-k1,-f);
        ins(x,t,k2-k1,f);        
    }
}

int bfs(int st,int ed)
{
    while(!q.empty()) q.pop();
    memset(in,0,sizeof(in));
    memset(dis,63,sizeof(dis));
    memset(flow,0,sizeof(flow));
    memset(pre,-1,sizeof(pre));
    q.push(st);
    dis[st]=0;flow[st]=INF;in[st]=1;
    while(!q.empty())
    {
        int x=q.front();in[x]=0;q.pop();
        for(int i=first[x];i!=-1;i=a[i].next)
        {
            int y=a[i].y;
            if(a[i].d && dis[y]>dis[x]+a[i].f)
            {
                dis[y]=dis[x]+a[i].f;
                flow[y]=minn(flow[x],a[i].d);
                pre[y]=i;
                if(!in[y]) in[y]=1,q.push(y);
            }
        }
    }
    return flow[ed];
}

void dinic(int st,int ed)
{
    int k;
    fl=0;cl=0;
    while(k=bfs(st,ed))
    {
        bk=1;
        fl+=k;cl+=dis[ed]*k;
        int p=ed;
        while(p!=st)
        {
            a[pre[p]].d-=k;
            a[pre[p]^1].d+=k;
            p=a[pre[p]].x;
        }
    }
}

int main()
{
    int T,n,m,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        len=-1;sum=0;
        memset(first,-1,sizeof(first));
        s=0,t=2*n+1;
        for(int i=1;i<=n;i++)
            addedge(A(i),B(i),k,k,0);
        for(int i=1;i<=m;i++)
        {
            int x,y,d;
            scanf("%d%d%d",&x,&y,&d);
            x++,y++;
            addedge(B(x),A(y),0,1,d);
        }
        // for(int i=0;i<len;i+=2)
            // printf("%d --> %d  d = %d  f = %d
",a[i].x,a[i].y,a[i].d,a[i].f);
        dinic(s,t);
        if(fl==sum) printf("%d
",cl);
        else printf("-1
");
    }
    return 0;
}

LA2197

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 using namespace std;
  7 
  8 const int N=300,INF=(int)1e9;
  9 int s,t,len,first[N],dis[N],fa[N];
 10 bool c[N][N];
 11 struct node{
 12     int x,y,d,next;
 13 }a[100010];
 14 queue<int> q;
 15 
 16 int minn(int x,int y){return x<y ? x:y;}
 17 
 18 int findfa(int x)
 19 {
 20     if(fa[x]!=x) fa[x]=findfa(fa[x]);
 21     return fa[x];
 22 }
 23 
 24 void ins(int x,int y)
 25 {
 26     a[++len].x=x;a[len].y=y;a[len].d=1;
 27     a[len].next=first[x];first[x]=len;
 28     a[++len].x=y;a[len].y=x;a[len].d=0;
 29     a[len].next=first[y];first[y]=len;
 30 }
 31 
 32 int bfs(int st,int ed)
 33 {
 34     while(!q.empty()) q.pop();
 35     memset(dis,-1,sizeof(dis));
 36     q.push(st);
 37     dis[st]=0;
 38     while(!q.empty())
 39     {
 40         int x=q.front();q.pop();
 41         for(int i=first[x];i!=-1;i=a[i].next)
 42         {
 43             int y=a[i].y;
 44             if(a[i].d && dis[y]==-1)
 45             {
 46                 dis[y]=dis[x]+1;
 47                 q.push(y);
 48             }
 49         }
 50     }
 51     return (dis[ed]!=-1);
 52 }
 53 
 54 int dfs(int x,int ed,int flow)
 55 {
 56     int r=0,p;
 57     if(x==ed) return flow;
 58     for(int i=first[x];i!=-1;i=a[i].next)
 59     {
 60         int y=a[i].y;
 61         if(dis[y]==dis[x]+1 && a[i].d)
 62         {
 63             p=minn(flow-r,a[i].d);
 64             p=dfs(y,ed,p);
 65             r+=p;
 66             a[i].d-=p;
 67             a[i^1].d+=p;
 68         }
 69         if(r==flow) break;
 70     }
 71     if(!r) dis[x]=-1;
 72     return r;
 73 }
 74 
 75 int dinic(int st,int ed)
 76 {
 77     int k,ans=0;
 78     while(k=bfs(st,ed))
 79         ans+=dfs(st,ed,INF);
 80     return ans;
 81 }
 82 
 83 int main()
 84 {
 85     int T;
 86     scanf("%d",&T);
 87     while(T--)
 88     {
 89         int n,m1,m2,x,y;
 90         scanf("%d%d%d",&n,&m1,&m2);
 91         s=0,t=2*n+1,len=-1;
 92         memset(first,-1,sizeof(first));
 93         memset(c,0,sizeof(c));
 94         for(int i=1;i<=n;i++) fa[i]=i;
 95         for(int i=1;i<=m1;i++)
 96         {
 97             scanf("%d%d",&x,&y);
 98             c[x][y]=1;
 99         }
100         for(int i=1;i<=m2;i++)
101         {
102             scanf("%d%d",&x,&y);
103             fa[findfa(x)]=findfa(y);
104         }
105         for(int i=1;i<=n;i++) fa[i]=findfa(i);
106         for(int i=1;i<=n;i++)
107             for(int j=1;j<=n;j++)
108             {
109                 if(c[i][j]) ins(i,n+j);
110                 else 
111                 {
112                     for(int k=1;k<=n;k++)
113                         if(fa[i]==fa[k] && c[k][j]) {ins(i,n+j);break;}
114                 }
115             }
116         int rl=len;
117         for(int i=1;i<=n;i++) ins(s,i);
118         for(int i=n+1;i<=2*n;i++) ins(i,t);
119         // for(int i=0;i<=len;i+=2) printf("%d -- > %d  %d
",a[i].x,a[i].y,a[i].d);
120         int l=0,r=n*n;
121         while(l!=r)
122         {
123             int k=(l+r+1)>>1;
124             for(int i=0;i<=rl;i+=2) a[i].d=1,a[i^1].d=0;
125             for(int i=rl+1;i<=len;i+=2) a[i].d=k,a[i^1].d=0;
126             if(dinic(s,t)==n*k) l=k;
127             else r=k-1;
128         }
129         printf("%d
",l);
130     }
131     return 0;
132 }

hdu3081

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<queue>
  6 using namespace std;
  7 
  8 const int N=110,M=550,INF=(int)1e9;
  9 int s,t,sl,len,first[N],dis[N],in[N],out[N],g[N],sk[N];
 10 bool vis[N];
 11 struct node{
 12     int x,y,d,next,id;
 13     bool temp,bk;
 14 }a[100010],b[M];
 15 queue<int> q;
 16 int minn(int x,int y){return x<y ? x:y;}
 17 
 18 void ins(int x,int y,int d,bool p)
 19 {
 20     a[++len].x=x;a[len].y=y;a[len].d=d;
 21     a[len].next=first[x];first[x]=len;
 22     if(!p)
 23     {
 24         a[++len].y=x;a[len].x=y;a[len].d=0;
 25         a[len].next=first[y];first[y]=len;        
 26     }
 27 }
 28 
 29 bool bfs(int st,int ed)
 30 {
 31     while(!q.empty()) q.pop();
 32     memset(dis,-1,sizeof(dis));
 33     q.push(st);dis[st]=0;
 34     while(!q.empty())
 35     {
 36         int x=q.front();q.pop();
 37         for(int i=first[x];i!=-1;i=a[i].next)
 38         {
 39             int y=a[i].y;
 40             if(a[i].d && dis[y]==-1)
 41             {
 42                 dis[y]=dis[x]+1;
 43                 q.push(y);
 44             }
 45         }
 46     }
 47     return (dis[ed]!=-1);
 48 }
 49 
 50 int dfs(int x,int ed,int flow)
 51 {
 52     int r=0;
 53     if(x==ed) return flow;
 54     for(int i=first[x];i!=-1;i=a[i].next)
 55     {
 56         int y=a[i].y;
 57         if(dis[y]==dis[x]+1 && a[i].d)
 58         {
 59             int p=minn(flow-r,a[i].d);
 60             p=dfs(y,ed,p);
 61             r+=p;
 62             a[i].d-=p;
 63             a[i^1].d+=p;
 64         }
 65         if(r==flow) break;
 66     }
 67     if(r==0) dis[x]=-1;
 68     return r;
 69 }
 70 
 71 int dinic(int st,int ed)
 72 {
 73     int k,ans=0;
 74     while(k=bfs(st,ed))
 75         ans+=dfs(st,ed,INF);
 76     return ans;
 77 }
 78 
 79 void find(int x)
 80 {
 81     for(int i=first[x];i!=-1;i=a[i].next)
 82     {
 83         int y=a[i].y;
 84         if(!vis[y] || !a[i].bk) continue;
 85         a[i].bk=0;
 86         find(y);
 87     }
 88     sk[++sl]=x,vis[x]=0;
 89 }
 90 
 91 int main()
 92 {
 93     int T,n,m,sum,cas=0;char c;bool bk;
 94     scanf("%d",&T);
 95     while(T--)
 96     {
 97         bk=1;
 98         scanf("%d%d",&n,&m);
 99         len=-1;
100         memset(first,-1,sizeof(first));
101         memset(in,0,sizeof(in));
102         memset(out,0,sizeof(out));
103         s=0,t=n+1;sum=0;
104         for(int i=1;i<=m;i++)
105         {
106             scanf("%d%d %c",&b[i].x,&b[i].y,&c);
107             in[b[i].y]++;out[b[i].x]++;
108             if(c=='U') b[i].temp=1;
109             else b[i].temp=0;
110             b[i].bk=0;
111         }
112         for(int i=1;i<=n;i++)
113         {
114             int d=in[i]-out[i];
115             if(d&1) {bk=0;break;}
116             if(d<0) ins(s,i,(-d)/2,0),sum+=(-d)/2;
117             if(d>0) ins(i,t,d/2,0);            
118         }
119         if(bk)
120         {
121             for(int i=1;i<=m;i++)
122             {
123                 if(!b[i].temp) continue;
124                 ins(b[i].x,b[i].y,1,0);
125                 b[i].id=len-1;
126             }
127             if(dinic(s,t)!=sum) bk=0;
128         }
129         if(cas) printf("
");cas++;
130         if(!bk) printf("No euler circuit exist
");
131         else
132         {
133             for(int i=1;i<=m;i++)
134             {
135                 if(b[i].temp) b[i].bk=a[b[i].id].d;
136                 else b[i].bk=1;
137             }
138             len=-1;
139             memset(first,-1,sizeof(first));
140             for(int i=1;i<=m;i++)
141                 if(b[i].bk) ins(b[i].x,b[i].y,1,1);
142                 else ins(b[i].y,b[i].x,1,1);
143             sl=0;memset(vis,1,sizeof(vis));
144             for(int i=0;i<=len;i++) a[i].bk=1;
145             find(1);
146             for(int i=sl;i>=1;i--) printf("%d ",sk[i]);printf("
");
147         }
148     }
149     return 0;
150 }

uva10735

题号	题目	题意	题解	备注
poj2396	Budget	一个n*m的矩阵，给定每一行的和以及每一列的和，然后给定多个限制，即某个格子的上下界，要求一个可行的方案。	建n个点表示行，m个点表示列，原图源汇点s、t。 s连到表示第i行的点，上下界都为sum[i]（行）表示第i列的点连到t，上下界都为sum[i]（列）然后表示第i行的点x和表示第j行的点y中间连一条边，上下界就是约束。错了很久，注意： 1.边数要足够大 2.p数组一开始没有清空 3.dfs的优化（不断找，用r储存已用的流量）快超级多。	上下界网络流可行流矩阵模型模板题
LA5095	Transportation	一个n个点、m条边的有向图，1为起点，n为终点，要从起点运k个物体到终点，每条边的费用与流量关系：f=ax^2，问最小费用。	重新开一个源点，源点到1有一条流量为k、费用为0的边，然后跑最小费用最大流，如果最大流等于k则可行。	最小费用最大流 f=ax^i（i为自然数）模型模板题
LA3487	Duopoly	A、B两个公司要买一些资源（他们自己买的资源不会重复），一个资源只能卖给一个公司。问最大收益。	方法一把每个询问看成一个点，然后A的询问连源点，B的询问连汇点，如果AB间的某个询问有矛盾就在它们中间连一条无限大的边，ans=sum-最小割。方法二：对于每个询问，新建一个点x，如果是Ａ就源点连向这个点，流量为价钱ｐ，然后连向这个询问所要求买的资源c[i]，流量为INF。如果是B则反过来，连向汇点。	最小割一个费用/流量对应多个点模板题
LA5131	Chips Challenge	给定一个矩阵，每个格子有三种情况——不能填、能填、一定要填，要求填最多的格子，使第i行的总和等于第i列的总和，并且填的格子数不能大于总数的A/B。	构图：在表示第i行的点x和表示第i列的点y间连一条(y,x)的边，费用为1，然后跑最大费用流。详见博客。	最大费用循环流模板题
LA2796	Concert Hall Scheduling	你有2个房间，有365天，有n个人找你租房，第i个人要从第xi到第yi天要一个房(任意一个),付wi的钱，求怎样安排收的钱最多	建365个点，连（i,i+1,2,0）的边（流量2（2个房间），费用0），源点连1，流量2费用0，365连汇点，流量2费用0。然后对于一个询问（xi,yi,wi）,连(xi,yi+1,2,wi)的边，注意是yi+1，不然yi这个点可能同时作为别人的起点，然后重复就WA了。跑一遍最大费用流。	最大费用流区间模型
uva1515	Pool construction	给一个m*n的矩阵，每个格子中是#和.两个符号之一，分别代表草和洞。现在要将洞给围起来（将草和洞分离），每条边需花费b元（即将一个洞包起来需要4边，将2个连续的洞包起来需要6边，省了2条边）。有个特殊能力，能将洞变成草，花费f。当然也能将草变成洞，花费d。围起洞来需要多少花费。矩阵四周最边边的格子都必须是草，即出现洞就必须转草。	s代表草，t代表洞；对于每个点x，如果是草，建边(s,x,0)，(x,t,d); 如果是洞，建边(s,x,f),(x,t,0) 如果一定要选，那到另一个的流量就是INF（代价无穷大）对于每对相邻的点(x,y),建(x,y,b),(y,x,b) 这样就可以保证当x、y是不同的东西，最小割的时候就必须加上b的代价，那就是洞包起来的代价。	二分图模型最小割
LA2197	Paint the Roads	n个点m条边的带权有向图，现在要将某些边涂上颜色，使得每个点恰好在k个有颜色的环上，总费用最小。	题意->每个点每一秒流入和流出的流量都是k->最小费用循环流把一个点拆成两个点，这两个点之间连一条边，上下界都是k，然后跑有上下界的最小费用循环流。对于每条边(x,y,k1,k2,f)，拆成：(x,y,k1,k1,f)(再按上下界拆边，即(s,y,k1,f) (x,t,k1,f)),(y,x,k2-k1,-f),(s,y,k2-k1,0),(x,t,k2-f1,f),用k2的和判满流。	最小费用循环流拆点
hdu3081	Marriage Match II	n个女生与n个男生配对，每个女生只能配对某些男生，有些女生相互是朋友，每个女生也可以跟她朋友能配对的男生配对。每次配对，每个女生都要跟不同的男生配对且每个女生都能配到对。问最多能配对几轮。(n<=100)	二分答案k，用并查集建边，每对可配对的男生与女生之间连一条流量为1的边，源点到每个女生连一条k的边，汇点连每个男生，流量为k。跑最大流。 WA了一中午，对拍都看不出错，然后是一个i打成了x，泪目。	最大流二分
uva10735	Euler Circuit	给定一个混合图（有有向边和无向边），然后要你求一条欧拉回路（遍历所有边后回到出发点）。	1.欧拉回路建图，给无向边定向。最终要是in[i]==out[i]，那就先给无向边随便定向，d[i]=in[i]-out[i],若d[i]为奇数则无解（反一条边，d[i]会变化2）。对于d[i]>0，则最多要改d[i]/2条入边，(i,t,d[i]/2) 对于d[i]<0，则最多要该(-d[i])/2条出边，(s,i,(-d[i])/2) 每条无向边最多更改一次，(x,y,1) 跑最大流，满流则有解。 2.输出欧拉回路（套圈算法）。随便从一个点开始遍历，走出一个圈，但是有一些边可能还没走，又有一个圈。做法就是起点开始遍历，dfs遍历其相邻的点，如果一个点没有相邻点了就压到栈里。倒序输出。	最大流欧拉回路构图