HDU 1853Cyclic Tour（网络流之最小费用流） - c++编程基础

TOP

HDU 1853Cyclic Tour（网络流之最小费用流）

2015-11-21 01:58:02 来源: 作者: 【大中小】浏览:6次

题目地址：HDU1853

费用流果然好神奇。。还可以用来判断环。。。如果每个点都是环的一部分而且每个点只能用到一次的话，那每个点的初度入度都是1，这就可以利用网络流来解决，只要拆点令其流量为1，就限制了每个点只能用一次，每次左边的连到右边的，就相当于左边点的一次初度和右边的点的一次入度，很容易想象出来。最后只要判断总流量是否为n即可，因为如果总流量为n的话，说明每个点都出了一次度，每个点都入了一次度，而且由于拆点的流量限制，充分说明了每个点的初度入度都是1.进而说明了每个点都在环里。然后输出最后的最小费用流即为最短距离。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include
          #include 
          
            using namespace std; const int INF=0x3f3f3f3f; int head[300], s, t, cnt, flow, cost; int vis[300], d[300], q[100000], cur[300]; struct node { int u, v, cap, cost, next; }edge[100000]; void add(int u, int v, int cap, int cost) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].cost=cost; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].cost=-cost; edge[cnt].next=head[v]; head[v]=cnt++; } int spfa() { memset(d,INF,sizeof(d)); memset(vis,0,sizeof(vis)); d[s]=0; cur[s]=-1; int f1=0 ,f2=0, i, minflow=INF; q[f1++]=s; while(f1>=f2) { int u=q[f2++]; vis[u]=0; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(d[v]>d[u]+edge[i].cost&&edge[i].cap) { d[v]=d[u]+edge[i].cost; if(minflow>edge[i].cap) { minflow=edge[i].cap; } cur[v]=i; if(!vis[v]) { q[f1++]=v; vis[v]=1; } } } } if(d[t]==INF) return 0; flow+=minflow; cost+=minflow*d[t]; for(i=cur[t];i!=-1;i=cur[edge[i^1].v]) { edge[i].cap-=minflow; edge[i^1].cap+=minflow; } return 1; } int main() { int n, m, i, a, b, c; while(scanf("%d%d",&n,&m)!=EOF) { memset(head,-1,sizeof(head)); cnt=0; s=0; t=2*n+1; flow=0; cost=0; for(i=1;i<=n;i++) { add(s,i,1,0); add(i+n,t,1,0); } while(m--) { scanf("%d%d%d",&a,&b,&c); add(a,b+n,1,c); } while(spfa()); if(flow!=n) printf("-1\n"); else printf("%d\n",cost); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：J2EE的13个规范之JDBC	下一篇：HDU 4508 湫湫系列故事――减肥记..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: