首页 > 代码库 > HDU 3987 && DINIC
HDU 3987 && DINIC
很容易发现是网络流的题目，但最少边怎么求呢？初时想不到，但画图后忽然发现可以这样：
求一次网络流最小割后，把满流的边置1，不满流的置INF。再求一次最大流即可。
为什么呢？
是否会存在一些边当前不满流，但有可能是最少边数最少割的边呢？否。因为按照DINIC的求法，每次都是增广容量最少的路，若当前不满流，则必定不是最小割的边，所以只需在满流的边，即可组成最小割的边寻找最少边就可以了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 7 const int INF=0x3f3f3f3f; 8 const int MAXN=1050; 9 const int MAXM=400000; 10 11 struct Node{ 12 int from,to,next; 13 int cap; 14 }edge[MAXM]; 15 int tol; 16 17 int dep[MAXN]; 18 int head[MAXN]; 19 20 int n,m; 21 void init(){ 22 tol=0; 23 memset(head,-1,sizeof(head)); 24 } 25 void addedge(int u,int v,int w){ 26 edge[tol].from=u; 27 edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u]; 28 head[u]=tol++; 29 edge[tol].from=v; 30 edge[tol].to=u; 31 edge[tol].cap=0; 32 edge[tol].next=head[v]; 33 head[v]=tol++; 34 } 35 36 int BFS(int start,int end){ 37 int que[MAXN]; 38 int front,rear; front=rear=0; 39 memset(dep,-1,sizeof(dep)); 40 que[rear++]=start; 41 dep[start]=0; 42 while(front!=rear) { 43 int u=que[front++]; 44 if(front==MAXN)front=0; 45 for(int i= head[u];i!=-1; i=edge[i].next){ 46 int v=edge[i].to; 47 if(edge[i].cap>0&& dep[v]==-1){ 48 dep[v]=dep[u]+1; 49 que[rear++]=v; 50 if(rear>=MAXN) rear=0; 51 if(v==end)return 1; 52 } 53 } 54 } 55 return 0; 56 } 57 int dinic(int start,int end){ 58 int res=0; 59 int top; 60 int stack[MAXN]; 61 int cur[MAXN]; 62 while(BFS(start,end)){ 63 memcpy(cur,head, sizeof(head)); 64 int u=start; 65 top=0; 66 while(1){ 67 if(u==end){ 68 int min=INF; 69 int loc; 70 for(int i=0;i<top;i++) 71 if(min>edge [stack[i]].cap) { 72 min=edge [stack[i]].cap; 73 loc=i; 74 } 75 for(int i=0;i<top;i++){ 76 edge[stack[i]].cap-=min; 77 edge[stack[i]^1].cap+=min; 78 } 79 res+=min; 80 top=loc; 81 u=edge[stack[top]].from; 82 } 83 for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next) 84 if(edge[i].cap!=0 && dep[u]+1==dep[edge[i].to]) 85 break; 86 if(cur[u] !=-1){ 87 stack [top++]= cur[u]; 88 u=edge[cur[u]].to; 89 } 90 else{ 91 if(top==0) break; 92 dep[u]=-1; 93 u= edge[stack [--top] ].from; 94 } 95 } 96 } 97 return res; 98 } 99 100 int main(){101 int T,cas=0;102 int u,v,w,d;103 scanf("%d",&T);104 while(T--){105 init();106 cas++;107 scanf("%d%d",&n,&m);108 for(int i=0;i<m;i++){109 scanf("%d%d%d%d",&u,&v,&w,&d);110 if(d){111 addedge(v,u,w);112 }113 addedge(u,v,w);114 }115 dinic(0,n-1);116 for(int i=0;i<tol;i+=2){117 if(edge[i].cap==0){118 edge[i].cap=1; edge[i^1].cap=0;119 }120 else {121 edge[i].cap=INF;122 edge[i^1].cap=0;123 }124 }125 int ans=dinic(0,n-1);126 printf("Case %d: ",cas);127 printf("%d\n",ans);128 }129 return 0;130 }
DINIC的模板
1 const int INF=0x3f3f3f3f; 2 const int MAXN=1050; 3 const int MAXM=400000; 4 5 struct Node{ 6 int from,to,next; 7 int cap; 8 }edge[MAXM]; 9 int tol;10 11 int dep[MAXN];12 int head[MAXN];13 14 int n,m;15 void init(){16 tol=0;17 memset(head,-1,sizeof(head));18 }19 void addedge(int u,int v,int w){20 edge[tol].from=u;21 edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u];22 head[u]=tol++;23 edge[tol].from=v;24 edge[tol].to=u;25 edge[tol].cap=0;26 edge[tol].next=head[v];27 head[v]=tol++;28 }29 30 int BFS(int start,int end){31 int que[MAXN];32 int front,rear; front=rear=0;33 memset(dep,-1,sizeof(dep));34 que[rear++]=start;35 dep[start]=0;36 while(front!=rear) {37 int u=que[front++];38 if(front==MAXN)front=0;39 for(int i= head[u];i!=-1; i=edge[i].next){40 int v=edge[i].to;41 if(edge[i].cap>0&& dep[v]==-1){42 dep[v]=dep[u]+1;43 que[rear++]=v;44 if(rear>=MAXN) rear=0;45 if(v==end)return 1;46 }47 }48 }49 return 0;50 }51 int dinic(int start,int end){52 int res=0;53 int top;54 int stack[MAXN];55 int cur[MAXN];56 while(BFS(start,end)){57 memcpy(cur,head, sizeof(head));58 int u=start;59 top=0;60 while(1){61 if(u==end){62 int min=INF;63 int loc;64 for(int i=0;i<top;i++)65 if(min>edge [stack[i]].cap) {66 min=edge [stack[i]].cap;67 loc=i;68 }69 for(int i=0;i<top;i++){70 edge[stack[i]].cap-=min;71 edge[stack[i]^1].cap+=min;72 }73 res+=min; 74 top=loc; 75 u=edge[stack[top]].from;76 }77 for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next)78 if(edge[i].cap!=0 && dep[u]+1==dep[edge[i].to])79 break;80 if(cur[u] !=-1){81 stack [top++]= cur[u];82 u=edge[cur[u]].to;83 }84 else{85 if(top==0) break;86 dep[u]=-1;87 u= edge[stack [--top] ].from;88 }89 }90 }91 return res;92 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。