題意：
? ? ?網選賽的一個題目，當時各種超時各種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 费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。