HDU 3315 My Brute(费用流） - c++编程基础

TOP

HDU 3315 My Brute(费用流）

2015-07-20 17:50:35 来源: 作者: 【大中小】浏览:1次

题目地址：HDU 3315

这个题的思路完全是自己想出来的，自我感觉挺巧妙的。。。（大牛勿喷。。。）对大胆建图又多了一份信心。

具体思路是构造一个二分图，Si连源点，Xi连汇点，流量都是1，费用0.然后当Si可以赢Xj的时候，就对这两人连一条边，费用值为-Vi*1000，如果i==j的话，费用值就再减1，因为题目要求尽量不改变原先的顺序，所以说应该尽量让序号相同的对打。而费用值减1的话，会优先考虑序号相同的，而且让费用扩大了1000倍，此时也不会改变主要的分数因素大小。同理，输的话，费用值为Vi*1000，如果i==j的话，费用值同样减1。

最后算出的最大费用cost/1000就是正确的费用值，cost%1000就是改变顺序了的数目。然后做相应判断与计算即可。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; const int INF=0x3f3f3f3f; int head[1000], source, sink, cnt, fei[10000], q[10000], flow, cost; int d[1000], vis[1000], cur[1000], f[1000]; struct node { int u, v, cap, cost, next; }edge[1000000]; 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)); queue
             
              q; q.push(source); d[source]=0; f[source]=INF; cur[source]=-1; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int 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; f[v]=min(f[u],edge[i].cap); cur[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(d[sink]==INF) return 0; flow+=f[sink]; cost-=f[sink]*d[sink]; for(int i=cur[sink];i!=-1;i=cur[edge[i^1].v]) { edge[i].cap-=f[sink]; edge[i^1].cap+=f[sink]; } return 1; } void mcmf(int n) { flow=cost=0; while(spfa()) ; if(cost/1000<=0) { printf("Oh, I lose my dear seaco!\n"); //printf("%d\n",cost); } else { int x=cost/1000, y=cost%1000; printf("%d %.3lf%%\n",x,y*100.0/n); } } int pan(int x1, int x2, int y1, int y2) { while(1) { x2-=y1; if(x2<=0) return 1; x1-=y2; if(x1<=0) return 0; } } int main() { int n, i, V[100], H[100], P[100], A[100], B[100], j; while(scanf("%d",&n)!=EOF&&n) { for(i=1;i<=n;i++) scanf("%d",&V[i]); for(i=1;i<=n;i++) scanf("%d",&H[i]); for(i=1;i<=n;i++) scanf("%d",&P[i]); for(i=1;i<=n;i++) scanf("%d",&A[i]); for(i=1;i<=n;i++) scanf("%d",&B[i]); memset(head,-1,sizeof(head)); cnt=0; source=0; sink=2*n+1; for(i=1;i<=n;i++) { add(source,i,1,0); add(i+n,sink,1,0); } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(pan(H[i],P[j],A[i],B[j])) { if(i==j) add(i,j+n,1,-V[i]*1000-1); else add(i,j+n,1,-V[i]*1000); } else { if(i==j) add(i,j+n,1,V[i]*1000-1); else add(i,j+n,1,V[i]*1000); } } } mcmf(n); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：CF 379D NewYearLetter [dp+暴力]	下一篇：UVA 11020 - Efficient Solutions..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: