題意:
? ? ? 給以一個無向圖,0 - n,警察在0,他們有k個警隊(duì),要派一些警隊(duì)去1--n個城市抓小偷,
問所有吧所有小偷全抓到然后在返回0的最小路徑和是多少,當(dāng)?shù)豬個城市被攻擊的時候他會通知i-1城市,也就是說要么同時消滅他倆,要么消滅i-1在消滅i;


思路:
? ? ? 經(jīng)典的費(fèi)用流建圖 ,先來一遍floyd處理下圖 ,首先虛擬出來源點(diǎn)s ,終點(diǎn)t ,超級源點(diǎn)ss,

建圖:

? ? ? ?from ? ? ? to ? ? ? ? cost ? ? ? ? ? flow

? ? ? ? ss ? ? ? ? s ? ? ? ? ?0 ? ? ? ? ? ? ?k ? ? ?//限制最多k個警隊(duì)
? ? ? ? s ? ? ? ? ?i ? ? ? ? ? map[0][i] ? 1 ? ? // 出發(fā)去
? ? ? ? i ? ? ? ? i + n ? ? ? -INF ? ? ? ? ? 1 ? ? //-INF 是為了保證每一個都得跑
? ? ? ? i + n ? ? t ? ? ? ? ?map[0][i] ? ?1 ? ? // 回家
? ? ? ? i + n ? ? j ? ? ? ? ?map[i][j] ? ? 1 ? ? //i < j ,收拾完i再去城鎮(zhèn)j收拾j

? ? ? ? ? s ? ? ? ?t ? ? ? ? ? ? ? 0 ? ? ? ? ? ?1 ? ? //用這個邊處理沒有出動的警隊(duì)

#include<stdio.h> #include<string.h> #include<queue>#define N_node 210 #define N_edge 20000 #define INF 10000000 using namespace std;typedef struct {int from ,to ,cost ,flow ,next; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mer[N_edge]; int s_x[N_node]; int map[N_node][N_node];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;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; }int MCMF_SPFA(int s ,int t ,int n) {int maxflow = 0,minflow;int mincost = 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;mincost += minflow * E[i].cost;}maxflow += minflow;}return mincost; }int minn(int x ,int y) {return x < y ? x : y; }void floyd(int n) {int i ,j ,k;for(k = 0 ;k <= n ;k ++)for(i = 0 ;i <= n ;i ++)for(j = 0 ;j <= n ;j ++)map[i][j] = minn(map[i][j] ,map[i][k] + map[k][j]); } int main () {int n ,m, i ,j ,K;int a ,b ,c;int ss ,s ,t;while(~scanf("%d %d %d" ,&n ,&m ,&K) && n + m + K){ss = 0 ,s = n + n + 1 ,t = n + n + 1 + 1;for(i = 0 ;i <= n ;i ++)for(j = 0 ;j <= n ;j ++){if(i == j) map[i][j] = 0;else map[i][j] = INF;}for(i = 1 ;i <= m ;i ++){scanf("%d %d %d" ,&a ,&b ,&c);map[a][b] = map[b][a] = minn(map[a][b] ,c);}floyd(n);memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= n ;i ++){add(s ,i ,map[0][i] ,1);add(i ,i + n ,-INF ,1);for(j = i + 1 ;j <= n ;j ++)add(i + n ,j ,map[i][j] ,1);add(i + n ,t ,map[i][0] ,1);}add(ss ,s ,0 ,K);add(s ,t ,0 ,K);int cost = MCMF_SPFA(ss ,t ,n + n + 1 + 1);printf("%d\n" ,cost + n * INF);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4411 经典费用里建图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。