題意:
? ? ? 給你一些任務,每個任務有自己的開始時間和需要多久能干完,還有就是每個任務都需要一些人,這些人有最多五個種類,各種類之間的人不能相互替換,但是某些工人干完這個活后如果可以在另一個任務還沒開始的時候趕過去,也可以幫那個任務干活,干的是自己的屬性的活,還有一個關鍵的點就是所有的任務必須人齊了才能干,最后問你最少要多少個人能把活干完..

思路:
? ? ? 費用流,就是在滿流(任務都必須干完)的前提下花費最少,一開始想的是吧每個點先拆成五個點,代表不同屬性的人,sb了,寫來寫去自己都蒙了,其實每個屬性的人之間沒有關系的話我們可以單獨算啊,就是跑5變費用流被,最后把他們加起來就好了,這樣就很容易寫了,下面說重點,怎么建圖.

首先要有一個超級源點和匯點,不解釋..


然后就是對于每一個點,我們要拆成兩個點(這兩個點之間沒有邊),這兩個點不是平時我們那種限流的點,一個是自己,另一個是用來連接自己可以給別的任務送人用的..對于每一個自己的點,我們連一條邊,流量inf,費用1,很容易理解,總部有無數的人,但是你要是用一個就得付出一個代價..

然后就是對于每一個拆出來的點,原點像它連接一條邊,流量是need,費用是0,因為當前的這個點最多能給別人提供need的人,而且是免費的...

最后就是找任務個任務之間的關系了,如果 work[i].p + work[i].d + dis(i ,j) <=?work[j].p ,就還來的及,那么就用i拆出來的那個點,去連接j的那個點...

大概就是這個樣子,自己表達能力不好,如果沒看懂畫一下子就明白了...?

#include<stdio.h> #include<string.h> #include<queue> #include<math.h>#define N_node 350 #define N_edge 30000 #define inf 1000000000 using namespace std;typedef struct {int from ,to ,cost ,flow ,next; }STAR;typedef struct {double x ,y;int p ,d;int need[6]; }WORK;STAR E[N_edge]; WORK work[N_node]; int list[N_node] ,tot; int mer[N_edge];void add(int a ,int b ,int 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; }bool spfa(int s ,int t ,int n) {int s_x[N_node];for(int i = 0 ;i <= n ;i ++)s_x[i] = inf;int mark[N_node] = {0};s_x[s] = 0;mark[s] = 1;queue<int>q;q.push(s);memset(mer ,255 ,sizeof(mer));while(!q.empty()){int tou ,xin;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(E[k].flow && s_x[xin] > s_x[tou] + E[k].cost){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; }int M_C_flow(int s, int t, int n) {int ans = 0 ,minflow;int maxflow = 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;ans += E[i].cost * minflow;}maxflow += minflow;}return ans; }int main () {int t ,n ,m ,i ,j;double sx ,sy;int a ,b, c ,d;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);scanf("%lf %lf" ,&sx ,&sy);n --;for(i = 1 ;i <= n ;i ++){scanf("%lf %lf %d %d" ,&work[i].x ,&work[i].y ,&work[i].p ,&work[i].d);for(j = 1 ;j <= m ;j ++)scanf("%d" ,&work[i].need[j]);}int ans = 0;for(int ii = 1 ;ii <= m ;ii ++){memset(list ,0 ,sizeof(list));tot = 1;int s = 0 ,t = n * 2 + 1;for(i = 1 ;i <= n ;i ++){add(s ,i ,1 ,inf) ,add(i ,s ,-1 ,0);add(i ,t ,0 ,work[i].need[ii]) ,add(t ,i ,-0 ,0);add(s ,i + n ,0 ,work[i].need[ii]) ,add(i + n ,s ,-0 ,0);}for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= n ;j ++){if(i == j) continue;double dis = pow(work[i].x - work[j].x ,2.0) + pow(work[i].y - work[j].y ,2.0);dis = sqrt(dis);if(work[i].p + work[i].d + dis <= work[j].p)add(i + n ,j ,0 ,inf) ,add(j ,i + n ,-0 ,0);}ans += M_C_flow(0 ,t ,t);}printf("%d\n" ,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu4494的全部內容，希望文章能夠幫你解決所遇到的問題。

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