首页 > 代码库 > hdu3488 / hdu3435 / hdu1853 最小费用最大流 圈 拆点
hdu3488 / hdu3435 / hdu1853 最小费用最大流 圈 拆点
题目大意：
在一个有向图中，求经过所有的点的圈的最短路径。
思路：
把i点拆为i和i+n两个点，源点S（2*n+1）连向i, 容量为1，边权为0。i+n连向汇点E(2*n+2),容量为1，边权为0。对于输入的边a,b,w,建立a->b+n的边，容量为1，边权为w。
然后就是用模版。
为什么能这样建图，其实我也不知道为什么。根本想不到可以这样建图。但是这样却是对的。只能是积累知识，下次遇到就会做了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int N =1010, M=50010,INF=0x3f3f3f3f; 8 struct node 9 { 10 int to, next, c ,f;//c是容量，f是费用 11 }edge[M]; 12 int head[N],dis[N],load[N],p[N]; 13 bool vis[N]; 14 int tot,flow,cost; 15 bool spfa(int S, int E,int n) 16 { 17 int que[N*10],qout,qin; 18 memset(vis,0,sizeof(vis)); 19 memset(load,-1,sizeof(load)); 20 memset(p,-1,sizeof(p)); 21 for(int i=0;i<=n;i++) 22 dis[i]=INF; 23 qin=qout=0; 24 que[qin++]=S; 25 dis[S]=0; 26 vis[S]=1; 27 while(qin!=qout) 28 { 29 int u=que[qout++]; 30 vis[u]=0; 31 for(int i=head[u];i!=-1;i=edge[i].next) 32 { 33 if(edge[i].c) 34 { 35 int v=edge[i].to; 36 if(dis[v]-dis[u]>edge[i].f) 37 { 38 dis[v]=dis[u]+edge[i].f; 39 p[v]=u; 40 load[v]=i; 41 if(!vis[v]) 42 { 43 vis[v]=1; 44 que[qin++]=v; 45 } 46 } 47 } 48 } 49 } 50 if(dis[E]==INF) return 0; 51 return 1; 52 } 53 void MCF(int S, int E,int n) 54 { 55 int u,mn; 56 flow=cost=0; 57 while(spfa(S,E,n)) 58 { 59 u=E; mn=INF; 60 while(p[u]!=-1) 61 { 62 mn=min(edge[load[u]].c, mn); 63 u=p[u]; 64 } 65 u=E; 66 while(p[u]!=-1) 67 { 68 edge[load[u]].c-=mn; 69 edge[load[u]^1].c+=mn; 70 u=p[u]; 71 } 72 cost+=dis[E]*mn; 73 flow+=mn; 74 } 75 } 76 void addedge(int a,int b,int c,int d) 77 { 78 edge[tot].to=b;edge[tot].c=c;edge[tot].f=d; 79 edge[tot].next=head[a];head[a]=tot++; 80 edge[tot].to=a;edge[tot].c=0;edge[tot].f=-d; 81 edge[tot].next=head[b];head[b]=tot++; 82 } 83 void init() 84 { 85 tot=0; 86 memset(head,-1,sizeof(head)); 87 } 88 int main() 89 { 90 //freopen("test.txt","r",stdin); 91 int n,m,k,i,j,w,cas,s,e; 92 scanf("%d",&cas); 93 while(cas--) 94 { 95 init(); 96 scanf("%d%d",&n,&m); 97 s=2*n+1;e=s+1; 98 while(m--) 99 {100 scanf("%d%d%d",&i,&j,&w);101 addedge(i,j+n,1,w);102 }103 for(i=1;i<=n;i++){104 addedge(s,i,1,0);105 addedge(i+n,e,1,0);106 }107 MCF(s,e,e);108 printf("%d\n",cost);109 }110 return 0;111 }
hdu3488 / hdu3435 / hdu1853 最小费用最大流 圈 拆点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。