Duopoly UVALive - 3487

網絡流·最小割

http://www.cnblogs.com/Konjakmoyu/p/5534304.html

題目大意：

有兩家公司都想向政府申請某些資源的使用權，并且他們都提供了一些申請清單，清單中含有申請費用和資源種類，同一家公司的申請清單之間不含有重複的資源。政府隻可以完整地接受和拒絕謀一份申請清單，問政府的最大收益是多少。

題解：

對于一組，建立一個點連源點（或彙點），流量為費用，再連向組内的全部點（流量為INF），最後跑一遍最小割即可。

Code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;

const int N = +;
const int M = +;
const int INF = ;

int n1,n2,S,T;

struct Edge{
    int to,next,flow,cap;
}e[M*];
int head[N], ec=;
void clear(){ memset(head,,sizeof(head)); ec=; }
void add(int a,int b,int c){
    ec++; e[ec].to=b; e[ec].cap=c; e[ec].flow=;
    e[ec].next=head[a]; head[a]=ec;
}
void add2(int a,int b,int c){
//  D(a); D(b); D(c); E;
    add(a,b,c); add(b,a,);
}

bool vis[N]; int d[N];
bool bfs(){
    memset(vis,false,sizeof(vis));
    queue<int> q; q.push(S); d[S]=; vis[S]=true;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(e[i].cap>e[i].flow && !vis[v]){
                vis[v]=true; d[v]=d[u]+;
                if(v==T) return true;
                q.push(v);
            }
        }
    } 
    return false;
}

int dfs(int u,int a){
    if(u==T || a==) return a;
    int flow=,f;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(d[v]==d[u]+ && (f=dfs(v,min(a,e[i].cap-e[i].flow)))){
            flow+=f; a-=f;
            e[i].flow+=f; e[i^].flow-=f;
            if(a==) break;
        }
    }
    if(a) d[u]=-;
    return flow;
}

int mxf(){
    int flow=;
    while(bfs()){
        flow+=dfs(S,INF);
    }
    return flow;
}

int main(){
    freopen("a.in","r",stdin);
    int tt; scanf("%d",&tt); getchar();
    for(int cas=;cas<tt;cas++){
        if(cas) puts("");
        int x,cost; char cc; int sum=; 
        clear(); S=; T=S+;
        scanf("%d",&n1); getchar();
        for(int i=;i<=n1;i++){
            scanf("%d",&cost); getchar();
            add2(S,i,cost); sum+=cost;
            while(scanf("%d%c",&x,&cc)){
                add2(i,x+,INF);
                if(cc=='\n') break;
            }
        }
        scanf("%d",&n2); getchar();
        for(int i=n1+;i<=n1+n2;i++){
            scanf("%d",&cost); getchar();
            add2(i,T,cost); sum+=cost;
            while(scanf("%d%c",&x,&cc)){
                add2(x+,i,INF);
                if(cc=='\n') break;
            }
        }
        int ans=mxf();
        ans=sum-ans;
        printf("Case %d:\n%d\n",cas+,ans);
    }
}