模板题：POJ1273
EK:#include#include #include #include using namespace std;int n,m,jy,map[305][305],c[305][305],a[305],p[305];bool vis[305];int M(int e){ int f=0; queue q; while(1){ memset(a,0,sizeof(a)); memset(vis,0,sizeof(vis)); a[1]=0x3fffffff;vis[1]=1;q.push(1); while(!q.empty()){ jy=q.front();q.pop(); for(int i=1;i<=e;i++){ if(!vis[i]&&map[jy][i]-c[jy][i]>0) { vis[i]=1; a[i]=min(a[jy],map[jy][i]-c[jy][i]); p[i]=jy; q.push(i); } } } if(a[e]==0)break; for(int i=e;i!=1;i=p[i]){ c[i][p[i]]-=a[e]; c[p[i]][i]+=a[e]; } f+=a[e]; } return f;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { memset(map,0,sizeof(map)); memset(c,0,sizeof(c)); memset(p,0,sizeof(p)); for(int i=1;i<=n;i++) { register int xx,yy,ee; scanf("%d%d%d",&xx,&yy,&ee); map[xx][yy]+=ee; } printf("%d\n",M(m)); } }
Dinic：
#include#include #include #include using namespace std;#define N 444int tot,next[N],first[N],w[N],v[N],n,m,ch[N];void add(int from,int to,int weight){ v[tot]=to;w[tot]=weight; next[tot]=first[from]; first[from]=tot++;}bool tell(){ memset(ch,-1,sizeof(ch)); queue q; q.push(1);ch[1]=0; while(!q.empty()){ int t=q.front();q.pop(); for(int i=first[t];~i;i=next[i]) if(w[i]&&ch[v[i]]==-1) q.push(v[i]),ch[v[i]]=ch[t]+1; } return ch[n]!=-1;}int zeng(int a,int b){ if(a==n)return b; int r=0; for(int i=first[a];~i&&b>=r;i=next[i]) if(ch[a]+1==ch[v[i]]&&w[i]){ int t=zeng(v[i],min(b-r,w[i])); w[i]-=t;w[i^1]+=t;r+=t; } if(!r)ch[a]=-1; return r;}int dinic(){ int ans=0,jy; while(tell())while(jy=zeng(1,0x3fffffff))ans+=jy; return ans;}int main(){ while(scanf("%d%d",&m,&n)!=EOF){ memset(first,-1,sizeof(first)); register int xx,yy,zz; tot=0; for(int i=1;i<=m;i++){ scanf("%d%d%d",&xx,&yy,&zz); add(xx,yy,zz);add(yy,xx,0); } printf("%d\n",dinic()); }}