HDU 3395 Special Fish(费用流) - c++编程基础

TOP

HDU 3395 Special Fish(费用流)

2015-07-20 17:42:10 来源: 作者: 【大中小】浏览:2次

题目地址：HDU 3395

刷了几道白书和CF上的非算法的智商题，感觉智商越来越接近负数了。。。还是先刷几道简单题缓缓。。

这题很简单，二分图模型，用费用流也可以，用KM也可以。不过需要注意的是这里是最大费用流，并不是最大费用最大流，区别在于是否是最大流，这题可以不是最大流，所以要当费用开始减少的时候停止继续流，来保证费用是最大的。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; const int INF=0x3f3f3f3f; int head[200], source, sink, cnt, flow, cost, a[200]; int f[200], cur[200], d[200], vis[200]; char s[200][200]; 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() { int i; memset(d,INF,sizeof(d)); memset(vis,0,sizeof(vis)); cur[source]=-1; f[source]=INF; d[source]=0; queue
             
              q; q.push(source); while(!q.empty()) { int u=q.front(); q.pop(); 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; 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; if(d[sink]>=0) return 0; flow+=f[sink]; cost+=f[sink]*d[sink]; for(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() { cost=flow=0; while(spfa()) ; printf("%d\n",-cost); } int main() { int n, i, j; while(scanf("%d",&n)!=EOF&&n) { memset(head,-1,sizeof(head)); cnt=0; source=0; sink=2*n+1; for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n;i++) { scanf("%s",s[i]); add(source,i,1,0); //add(i,sink,1,0); for(j=0;j


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：第k大的数(快速排序的划分过程)	下一篇：2014鞍山网络预选赛1004（贪心）h..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: