POJ - 3436 ACM Computer Factory(最大流，拆點)

題目連結

題目大意：要求經過每個點的流量不超過該點承載的流量上限，求最大流

思路：将a拆成a1和a2，a1作為輸入端，a2作為輸出端，a1->a2的邊權為流量上限

#include <bits/stdc++.h>

using namespace std;
const int N = *;
const int M = N*N;
int n,m,s,t,tot;
int head[N];
struct node{
    int u,nxt,cap,to,old;
}edge[M<<];
int cur[N],deep[N],p[N],in[N][],out[N][];
bool check(int a,int b){   //檢查是否可以a->b
    int i;
    for(i = ;i <= m;i ++){
        if(in[b][i]==&&out[a][i]==) return ;
        if(in[b][i]==&&out[a][i]==) return ;
    }
    return ;  //當時沒寫return 1本地居然過了，送出wa
}
void ae(int u,int v,int w){
    tot++;
    edge[tot].nxt = head[u];
    edge[tot].to = v;
    edge[tot].u = u;
    edge[tot].old = w;   //備份流量
    edge[tot].cap = w;
    head[u] = tot;
}
bool bfs(){
    memset(deep,-,sizeof(deep));
    queue<int>q;
    q.push(s);
    deep[s] = ;
    while(!q.empty()){
        int u = q.front();
        for(int i = head[u]; ~i;i = edge[i].nxt){
            int v = edge[i].to;
            if(deep[v]==-&&edge[i].cap>){
                q.push(v);
                deep[v] = deep[u]+;
                if(v==t) return ;
            }
        }
        q.pop();
    }
    return ;
}
int dfs(int u,int f){
    int flow = ,d;
    if(u==t||f==) return f;
    for(int &i = cur[u]; ~i;i = edge[i].nxt){
        int v = edge[i].to;
        if(deep[v]>deep[u]&&edge[i].cap>&&(d=dfs(v,min(f,edge[i].cap)))){
            edge[i].cap -= d;
            edge[i^].cap += d;
            f -= d;
            flow += d;
            if(!f) break;
        }
    }
    if(flow==) deep[u] = -;
    return flow;
}
int dinic(){
    int ans = ;
    while(bfs()){
        memcpy(cur, head, sizeof(head));
        ans += dfs(s,);
    }
    return ans;
}
int hs(int x){
    if(x%==) return x/+;
    else return x/;
}
int main()
{
    freopen("a.txt","r",stdin);
    ios::sync_with_stdio();
    cin>>m>>n;
    s = ;
    t = *n+;
    memset(head,-,sizeof(head));
    tot = -;
    int i,j;
    for(i = ;i <= n;i ++){
        cin>>p[*i];
        ae(*i-,*i,p[*i]);    //拆點連邊
        ae(*i,*i-,);
        for(j = ;j <= m;j ++) cin>>in[*i-][j];
        for(j = ;j <= m;j ++) cin>>out[*i][j];
    }
    p[] = ;
    for(i = ;i <= m;i ++) in[*n+][i] = ;
    for(i = ;i <= *n;i += )
        for(j = ;j <= *n+;j += ){
            if(check(i,j)){
                if(i-==j)continue; //防止重複建邊
                ae(i,j,p[i]);   //建圖,其實可以把p[i]改成1e9.....
                ae(j,i,);
            }
    }
    cout<<dinic()<<' ';
    int use = ,k;
    for(i = *n;i <= tot;i += ){
        if(k = edge[i].old-edge[i].cap){
            int u = edge[i].u;
            int v = edge[i].to;
            if(u==||v==*n+)continue;
            use ++;
        }
    }
    cout<<use<<endl;
    for(i = *n;i <= tot;i += ){   //跳過拆點産生的路徑
        if(k = edge[i].old-edge[i].cap){
            int u = edge[i].u;
            int v = edge[i].to;
            if(u==||v==*n+)continue;   //跳過s和t
            cout<<hs(u)<<' '<<hs(v)<<' '<<k<<endl;
        }
    }
    return ;
}