hdu 5045 费用流

题意：
     网选赛的一个题目，当时各种超时各种wa，哎！ 题意是有n个人m道题，每个人对每道题都有一个ac率，每相邻的n到题目必须n个人每人一道，顺序无所谓，上下的m%n道只要不出现一个人做两道就行，最后要求输出最大的ac率。


思路：

     第一眼就感觉是网络流，然后建了一个很复杂的图，结果各种超时，当时吧这个题目想的复杂了，队友后来用dp过了这个题目，感觉有点失落啊，回去了第二天早上又敲了一边费用流，ac了，哎！ 感觉没那么难受了，要是没看出来是网络流做不出来也就算了，看出来了，没敲出来，感觉耻辱啊，其实这个题目并不难，我们直接跑m/k+m%k次网络流就行了，具体看代码，一开始我的建图是跑一遍，然后给每个n个题目虚拟出n个人来，如果有余数在虚拟出n个人来，结果各种wa到现在也没找到原因，m/k+m%k次的细节具体看代码。

#include<stdio.h> #include<string.h> #include<queue>#define N_node 50 #define N_edge 500 #define INF 100000000 using namespace std;typedef struct {int from ,to ,next ,flow;double cost; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mer[N_edge]; double s_x[N_node]; double num[15][1100];void add(int a ,int b ,double c ,int d) {E[++tot].from = a;E[tot].to = b;E[tot].cost = c;E[tot].flow = d;E[tot].next = list[a];list[a] = tot;E[++tot].from = b;E[tot].to = a;E[tot].cost = -c;E[tot].flow = 0;E[tot].next = list[b];list[b] = tot; }bool spfa(int s ,int t ,int n) {int mark[N_node] = {0};for(int i = 0 ;i <= n ;i ++)s_x[i] = -INF;mark[s] = 1,s_x[s] = 0;queue<int>q;q.push(s);memset(mer ,255 ,sizeof(mer));while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] < s_x[tou] + E[k].cost && E[k].flow){s_x[xin] = s_x[tou] + E[k].cost;mer[xin] = k;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}}return mer[t] != -1; }double M_C_Flow(int s ,int t ,int n) {int maxflow = 0 ,minflow;double maxcost = 0;while(spfa(s ,t ,n)){minflow = INF;for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])if(minflow > E[i].flow) minflow = E[i].flow;for(int i = mer[t] ;i + 1 ;i = mer[E[i].from]){E[i].flow -= minflow;E[i^1].flow += minflow;maxcost += minflow * E[i].cost;}maxflow += minflow;}return maxcost; }int main () {int n ,m ,i ,j ,t ,cas = 1;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++)scanf("%lf" ,&num[i][j]);double Ans = 0;for(i = 1 ;i <= m ;i ++){if(i % n == 0){memset(list ,0 ,sizeof(list)) ,tot = 1; for(int ii = 1 ;ii <= n ;ii ++) add(0 ,ii ,0 ,1);for(int ii = 1 ;ii <= n ;ii ++)for(int jj = 1 ;jj <= n ;jj ++)add(ii ,n + jj ,num[ii][i-n+jj] ,1);for(int ii = 1 ;ii <= n ;ii ++) add(ii + n ,n + n + 1 ,0 ,1);Ans += M_C_Flow(0 ,n + n + 1 ,n + n + 1);} }if(m % n){memset(list ,0 ,sizeof(list)) ,tot = 1; for(int ii = 1 ;ii <= n ;ii ++) add(0 ,ii ,0 ,1);for(int ii = 1 ;ii <= n ;ii ++)for(int jj = 1 ;jj <= m % n ;jj ++)add(ii ,n + jj ,num[ii][m-(m%n)+jj] ,1);for(int ii = 1 ;ii <= n ;ii ++) add(ii + n ,n + n + 1 ,0 ,1);Ans += M_C_Flow(0 ,n + n + 1 ,n + n + 1);}printf("Case #%d: %.5lf\n" ,cas ++ ,Ans);}return 0; }

总结

以上是生活随笔为你收集整理的hdu 5045 费用流的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。