网络流才是正解!
查看原帖
网络流才是正解!
11363
Chtholly_Nota_Seniorious楼主2015/11/4 09:14
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAX 0x7f7f7f7f
#include<queue>
using namespace std;
const int s=1,t=2;
struct Edge{
    int to,cap;
    Edge *next,*oppo;
};
Edge *E[10],Pr[10];int cnt=0;
void addedge(int u,int v,int cap){
    Pr[++cnt].to=v;Pr[cnt].cap=cap;Pr[cnt].next=E[u];E[u]=&Pr[cnt];Pr[cnt].oppo=&Pr[cnt+1];
    Pr[++cnt].to=u;Pr[cnt].cap=0;Pr[cnt].next=E[v];E[v]=&Pr[cnt];Pr[cnt].oppo=&Pr[cnt-1];
}
void Init(){int x,y;
    scanf("%d%d",&x,&y);
    addedge(s,t,x);addedge(s,t,y);
}
int H[10];
bool Makelevel(){
    memset(H,MAX,sizeof(H));H[s]=0;
    queue<int> Q;Q.push(s);
    while(!Q.empty()){int u=Q.front();Q.pop();
        for(Edge *P=E[u];P;P=P->next){
            if(P->cap&&H[u]+1<H[P->to]){
                H[P->to]=H[u]+1;
                Q.push(P->to);
            }
        }
    }
    return H[t]!=MAX;
}
int extend(int u,int left){int r=0;
    if(u==t)return left;
    for(Edge *P=E[u];P&&r<left;P=P->next)
        if(P->cap&&H[u]+1==H[P->to]){int t;
            t=extend(P->to,min(P->cap,left-r));
            r+=t;P->cap-=t;P->oppo->cap+=t;
        }
    if(!r)H[u]=MAX;
    return r;
}
int Dinic(){int ans=0;
    while(Makelevel())ans+=extend(s,MAX);
    return ans;
}
int main(){
    Init();
    printf("%d\n",Dinic());
    return 0;
}
最大流才是正解
2015/11/4 09:14
加载中...