网络流做法...转bcbyql
查看原帖
网络流做法...转bcbyql
8397
shenxingyu楼主2015/11/4 12:17

[ codec]

#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;
}
[ /code]
2015/11/4 12:17
加载中...