题目链接:http://poj.org/problem?id=1273
分析:
Dinic模版题。
注意开空间的时候
这道题空间开太大会TLE。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include<cstdio>//BY:uncle-lu #include<cstring> #include<algorithm> using namespace std; struct node{ int v,next,val; }edge[410]; int head[202]; int deep[202]; int qu[210]; int n,m,cnt,ans; void add_edge(int x,int y,int val) { edge[++cnt].v=y; edge[cnt].val=val; edge[cnt].next=head[x]; head[x]=cnt; return ; } void all_init() { memset(head,0xff,sizeof(head)); cnt=0; ans=0; return ; } bool BFS() { memset(deep,0xff,sizeof(deep)); int heads=1,last=1; qu[heads]=1; deep[heads]=0; while(heads<=last) { int k=qu[heads]; for(int i=head[k];~i;i=edge[i].next) { if(deep[edge[i].v]==-1&&edge[i].val>0) { deep[edge[i].v]=deep[k]+1; qu[++last]=edge[i].v; } } heads++; } return deep[n]==-1 ? false:true; } int find_edge(int x,int low) { if(x==n)return low; int r=0; for(int i=head[x];~i;i=edge[i].next) { if(deep[edge[i].v]==deep[x]+1&&edge[i].val>0) { int t=find_edge(edge[i].v,min(low-r,edge[i].val)); edge[i].val-=t; edge[i^1].val+=t; r+=t; } if(low<=r)break; } return r; } void Dinic() { int k; while(BFS()) { while(1) { k=find_edge(1,0x3f3f3f); if(!k)break; ans+=k; } } return ; } int main() { int x,y,val; while(~scanf("%d%d",&m,&n)) { all_init(); for(int i=1;i<=m;++i) { scanf("%d%d%d",&x,&y,&val); add_edge(x,y,val); add_edge(y,x,0); } Dinic(); printf("%d\n",ans); } return 0; } |
