題意：
? ? ? ?給以一個(gè)圖，每個(gè)有向邊都有兩個(gè)權(quán)值，a,b其中a是保留這條邊的花費(fèi)，b是刪除這條邊的花費(fèi)，讓你刪去一些邊使圖滿(mǎn)足一下要求：
（1）只有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)
（2）所有的邊都是又向的（題目給的就是有向的）
（3）對(duì)于起點(diǎn)，出度 = 入度 + 1
（4）對(duì)于終點(diǎn)，入度 = 出度 + 1
（5）其他的點(diǎn) 出度 = 入度?
求滿(mǎn)足要求時(shí)的花費(fèi)最小。
?


思路：
? ? ? 仔細(xì)一看要求，貌似是在求一個(gè)“歐拉路”，（但是圖不一定是連通的），如果我們直接把t-s連起來(lái)就是在求所有出度=入度的最小了，也就是在求一些歐拉回路，第一反應(yīng)以為是混合歐拉呢，但是對(duì)于混合歐拉是用流而不是費(fèi)用流，而且混合歐拉里面也不設(shè)計(jì)到費(fèi)用，但是他們有很大的相似之處，這個(gè)題目做了好久，是因?yàn)樽约合氩怀鰜?lái)，同時(shí)網(wǎng)上的的解題報(bào)告很少，并且有的根本就寫(xiě)錯(cuò)了，還有就是網(wǎng)上沒(méi)有說(shuō)為什么，只有怎么建圖，所以想了好久才明白，思路不怎么好說(shuō)，我盡量去描述清楚，一邊建圖一遍說(shuō)吧。


（1）對(duì)于每一條邊，我們先選擇a,b中最小的加在sum里
//先選擇最小的，最為當(dāng)前的選擇，最后在用sum + 調(diào)整的代價(jià)就行了。
（2）如果a <= b ? sum += a ,連接邊b -> a,流量 1 ，費(fèi)用b - a
//a小我們選擇a，選擇a也就是我們當(dāng)前打算要這條邊，此時(shí)我們建立b->a是為了反悔的時(shí)候用的，b - a 是因?yàn)榉椿诘臅r(shí)候要花費(fèi)的代價(jià)是 b-a,因?yàn)橛幸徊糠质欠旁趕um里了。
因?yàn)槲覀冞x擇了這條邊，此時(shí)還要記錄度數(shù),我們雖然建的是b->a但度數(shù)要這樣，in[b]++,
out[a] ++,因?yàn)閎->a是為了反悔用的，我們的決策是在圖里建了一條a->b的邊，所以度數(shù)是那樣存的，不要弄混了。
（3）如果b < a ?sum += b ,連接邊a -> b,流量 1，費(fèi)用a - b
// b小于a ,當(dāng)前我們的選擇是不連這條邊，a -> b 是為了后悔的時(shí)候用的，后悔的時(shí)候我們只要在花費(fèi)a - b就可以把不連變成連了，有一個(gè)關(guān)鍵地方就是對(duì)于這種決策不要計(jì)算入度和出度，因?yàn)槲覀冞x擇的是不連邊，所以當(dāng)前的決策里面不設(shè)計(jì)到度數(shù)的改變。
（4）因?yàn)槲覀円褕D處理成所有點(diǎn)的出度=入度，所以我們還得吧in[s] ++ ,out[t] ++,
記住只是改度數(shù)，而沒(méi)有去連邊，只是虛擬的去連邊。
（5）最后我們要設(shè)立一個(gè)超級(jí)原點(diǎn)S和超級(jí)匯點(diǎn)T,對(duì)于所有點(diǎn)如果in[i] > out[i],
連接 S->i ,流量為in[i] - out[i] ,費(fèi)用 0，否則連接i->T,流量out[i] - in[i],
費(fèi)用0。
// 這個(gè)位置一定要理解好，不要和混合歐拉混了，混合歐拉是in[i] < out[i],連接
S->i,流量是 (out[i] - in[i]) / 2,混合歐拉是在調(diào)整（雙向邊的）涉及的度數(shù)，而咱們這個(gè)題目是為了調(diào)整單向邊涉及的點(diǎn)的度數(shù)，并且含有代價(jià)在里面，至于為什么連接S-i，和i->T的時(shí)候和混合歐拉是反的，是因?yàn)槲覀兘M開(kāi)始建圖的時(shí)候建的都是反邊，也就是建的都是反悔的時(shí)候才跑的邊，所以涉及到反向。
為了理解這個(gè)題目我畫(huà)了集合圖來(lái)方便大家理解，畫(huà)的垃圾忘諒解。




跑一邊S->T的費(fèi)用流就可以選擇出事l1反悔還是l2反悔了，如果對(duì)于l1,l2都不選，那么和這個(gè)差不多，只不過(guò)是虛線的方向邊了，S，T的連點(diǎn)再調(diào)換一下，如果都選我們跑邊S->T的目的是為了找出我們選擇的那一個(gè)，因?yàn)楫吘筶1,l2我們要選一個(gè)丟棄一個(gè)，如果是在之前我們的去最小決策就正好選了一個(gè)，丟棄了一個(gè)，那么此時(shí)的連個(gè)點(diǎn)出度=入度，也就沒(méi)必要跑費(fèi)用流了。

下面是代碼。

#include<stdio.h> #include<string.h> #include<queue>#define N_node 110 #define N_edge 5000 #define INF 1000000000 using namespace std;typedef struct {int from ,to ,next;int cost ,flow; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int s_x[N_node]; int mer[N_edge]; int in[N_node] ,out[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) {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 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 ss) {int maxflow ,mincost ,minflow;maxflow = 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 += E[i].cost * minflow;}maxflow += minflow;}if(maxflow != ss) return -1;return mincost; }int main () {int tt ,n ,m ,s ,t ,S ,T ,i;int cas = 1;int a ,b ,c ,d;scanf("%d" ,&tt);while(tt--){scanf("%d %d %d %d" ,&n ,&m ,&s ,&t);S = 0 ,T = n + 1;memset(list ,0 ,sizeof(list));tot = 1;memset(in ,0 ,sizeof(in));memset(out ,0 ,sizeof(out));in[s] ++ ,out[t] ++;int sum = 0;for(i = 1 ;i <= m ;i ++){scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);if(c <= d) {add(b ,a ,d - c ,1);sum += c;in[b]++ ,out[a] ++;}else{add(a ,b ,c - d ,1);sum += d;}}int ss = 0 ,sss = 0;for(i = 1 ;i <= n ;i ++){if(in[i] >= out[i]){add(S ,i ,0 ,in[i] - out[i]);ss += (in[i] - out[i]);}else{add(i ,T ,0 ,out[i] - in[i]);sss += (out[i] - in[i]);}}int ans = MCMF_Spfa(S ,T ,n + 1 ,ss);printf("Case %d: " ,cas ++);if(ans == -1 || ss != sss)puts("impossible");else printf("%d\n" ,ans + sum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4067 费用流（混合欧拉的宽展和延伸）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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