文章目錄

• T1：Going Home
• • 題目
  • 題解
  • CODE
• T2：Minimum Cost
• • 題目
  • 題解
  • CODE
• T3：工作安排
• • 題解
  • CODE

T1：Going Home

題目

On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.

Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a ‘.’ means an empty space, an ‘H’ represents a house on that point, and am ‘m’ indicates there is a little man on that point.

You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
Input
There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H’s and 'm’s on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.
Output
For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.
Sample Input
2 2
.m
H.
5 5
HH…m
…
…
…
mm…H
7 8
…H…
…H…
…H…
mmmHmmmm
…H…
…H…
…H…
0 0
Sample Output
2
10
28

題解

簡單題意就是一張圖，$H$表示一間屋子,$m$表示一個(gè)人，現(xiàn)在每個(gè)人要走到一間屋子里，消耗的費(fèi)用為兩點(diǎn)之間的距離，求每個(gè)都有一個(gè)房子的最小耗費(fèi)

---

是一道很裸的費(fèi)用流問題，這里本蒟蒻選擇了$EK+SPFA$
我們考慮建圖問題，先建一個(gè)超級源點(diǎn)s和一個(gè)超級匯點(diǎn)t，然后將所有房子$H$和s建邊，容量定義為1，邊權(quán)免費(fèi)，同理把所有人在的$m$和t建邊，容量為1，邊權(quán)免費(fèi)
最后的邊權(quán)決定于房子和人的搭配，這個(gè)邊權(quán)就是矩陣?yán)锩鎯蓚€(gè)點(diǎn)之間的距離，容量仍然是1，因?yàn)橐蝗艘婚g房

CODE

#include <queue> #include <cmath> #include <vector> #include <cstdio> #include <cstring> using namespace std; #define INF 1e9 #define MAXM 1000005 #define MAXN 100005 struct node {int v, w, next, c, flow; }edge[MAXM]; queue < int > q; vector < pair < int, int > > h, m; //處理出每一個(gè)房子和人所在的位置，第一關(guān)鍵字是行，第二關(guān)鍵字是列 int cnt, N, M, s, t; int head[MAXN], dis[MAXN], pre[MAXN]; bool vis[MAXN];void add ( int x, int y, int flow, int fi ) {edge[cnt].next = head[x];edge[cnt].v = y;edge[cnt].w = fi;edge[cnt].c = flow;edge[cnt].flow = 0;head[x] = cnt ++; }bool spfa () {memset ( vis, 0, sizeof ( vis ) ); memset ( dis, 0x7f, sizeof ( dis ) );memset ( pre, -1, sizeof ( pre ) );while ( ! q.empty() )q.pop();q.push( s );dis[s] = 0;vis[s] = 1;while ( ! q.empty() ) {int u = q.front();q.pop();vis[u] = 0;for ( int i = head[u];i != -1;i = edge[i].next ) {int v = edge[i].v;if ( dis[v] > dis[u] + edge[i].w && edge[i].c > edge[i].flow ) {dis[v] = dis[u] + edge[i].w;pre[v] = i;if ( ! vis[v] ) {q.push( v );vis[v] = 1;}}}} return pre[t] != -1; }void MCMF ( int &maxflow, int &mincost ) {maxflow = mincost = 0;while ( spfa() ) {int MIN = INF;for ( int i = pre[t];i != -1;i = pre[edge[i ^ 1].v] )MIN = min ( MIN, edge[i].c - edge[i].flow );for ( int i = pre[t];i != -1;i = pre[edge[i ^ 1].v] ) {edge[i].flow += MIN;edge[i ^ 1].flow -= MIN;mincost += MIN * edge[i].w;}maxflow += MIN;} }int Fabs ( int x ) {if ( x < 0 )return -x;return x; }int main() {while ( scanf ( "%d %d", &N, &M ) ) {if ( N == 0 && M == 0 )return 0;memset ( head, -1, sizeof ( head ) );cnt = 0;h.clear();m.clear(); for ( int i = 1;i <= N;i ++ ) {getchar();for ( int j = 1;j <= M;j ++ ) {char ch;scanf ( "%c", &ch );if ( ch == 'H' )h.push_back( make_pair ( i, j ) );if ( ch == 'm' )m.push_back ( make_pair ( i, j ) );}}s = 0;t = N * M + 1;for ( int i = 0;i < h.size();i ++ ) {//與超級源點(diǎn)建邊add ( s, ( h[i].first - 1 ) * M + h[i].second, 1, 0 );add ( ( h[i].first - 1 ) * M + h[i].second, s, 0, 0 );for ( int j = 0;j < m.size();j ++ ) {//屋子與人建邊，算是一種hash吧，畢竟每一個(gè)人和每一件房子都是獨(dú)一無二的add ( ( h[i].first - 1 ) * M + h[i].second, ( m[j].first - 1 ) * M + m[j].second, 1, Fabs ( h[i].first - m[j].first ) + Fabs ( h[i].second - m[j].second ) );add ( ( m[j].first - 1 ) * M + m[j].second, ( h[i].first - 1 ) * M + h[i].second, 0, - Fabs ( h[i].first - m[j].first ) - Fabs ( h[i].second - m[j].second ) );}}//與超級匯點(diǎn)建邊for ( int i = 0;i < m.size();i ++ ) {add ( ( m[i].first - 1 ) * M + m[i].second, t, 1, 0 );add ( t, ( m[i].first - 1 ) * M + m[i].second, 0, 0 );}int maxflow, mincost;MCMF ( maxflow, mincost );printf ( "%d\n", mincost );}return 0; }

T2：Minimum Cost

題目

Dearboy, a goods victualer, now comes to a big problem, and he needs your help. In his sale area there are N shopkeepers (marked from 1 to N) which stocks goods from him.Dearboy has M supply places (marked from 1 to M), each provides K different kinds of goods (marked from 1 to K). Once shopkeepers order goods, Dearboy should arrange which supply place provide how much amount of goods to shopkeepers to cut down the total cost of transport.

It’s known that the cost to transport one unit goods for different kinds from different supply places to different shopkeepers may be different. Given each supply places’ storage of K kinds of goods, N shopkeepers’ order of K kinds of goods and the cost to transport goods for different kinds from different supply places to different shopkeepers, you should tell how to arrange the goods supply to minimize the total cost of transport.
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, K (0 < N, M, K < 50), which are described above. The next N lines give the shopkeepers’ orders, with each line containing K integers (there integers are belong to [0, 3]), which represents the amount of goods each shopkeeper needs. The next M lines give the supply places’ storage, with each line containing K integers (there integers are also belong to [0, 3]), which represents the amount of goods stored in that supply place.

Then come K integer matrices (each with the size N * M), the integer (this integer is belong to (0, 100)) at the i-th row, j-th column in the k-th matrix represents the cost to transport one unit of k-th goods from the j-th supply place to the i-th shopkeeper.

The input is terminated with three "0"s. This test case should not be processed.
Output
For each test case, if Dearboy can satisfy all the needs of all the shopkeepers, print in one line an integer, which is the minimum cost; otherwise just output “-1”.
Sample Input
1 3 3
1 1 1
0 1 1
1 2 2
1 0 1
1 2 3
1 1 1
2 1 1

1 1 1
3
2
20

0 0 0
Sample Output
4
-1

題解

其實(shí)這道題有點(diǎn)考語文，輸入太**

我們考慮建一個(gè)超級源點(diǎn)和超級匯點(diǎn)，
在源點(diǎn)和店主的需求之間建一條邊，沒有中間商賺差價(jià)，容量自然就是店主的訂單量，
同理在供應(yīng)地點(diǎn)和超級匯點(diǎn)之間建一條邊，也沒有中間商賺差價(jià)，容量為供應(yīng)地點(diǎn)生產(chǎn)的產(chǎn)品數(shù)；
最后就是店主與供應(yīng)地點(diǎn)之間的建邊，因?yàn)橛?span id="ze8trgl8bvbq" class="katex--inline">$k$種不同的商品，所以一個(gè)供應(yīng)地點(diǎn)跟一個(gè)店主之間的成本也會隨著$k$的不一樣而改變，兩個(gè)解決辦法

1.把一個(gè)供應(yīng)地點(diǎn)拆成$k$個(gè)彼此獨(dú)立的供應(yīng)柜臺，專門只銷售一種類型的
由上面我們就可以發(fā)現(xiàn)，柜臺之間是彼此獨(dú)立的，互不影響，所以我們就有了第二種解決方案
2.把費(fèi)用流拆成$k$次一種商品的費(fèi)用流，每次費(fèi)用流都只處理一種商品，這樣建邊就不那么冗長

CODE

#include <queue> #include <cmath> #include <vector> #include <cstdio> #include <cstring> using namespace std; #define INF 1e9 #define MAXN 100 struct node {int v, w, next, c, flow; }edge[MAXN * MAXN]; queue < int > q; int cnt, n, m, k, s, t; int head[MAXN], dis[MAXN], pre[MAXN], need[MAXN][MAXN], num[MAXN][MAXN], matrix[MAXN][MAXN][MAXN]; bool vis[MAXN];void add ( int x, int y, int flow, int cost ) {edge[cnt].next = head[x];edge[cnt].v = y;edge[cnt].w = cost;edge[cnt].c = flow;edge[cnt].flow = 0;head[x] = cnt ++; }bool spfa () {memset ( vis, 0, sizeof ( vis ) ); memset ( dis, 0x7f, sizeof ( dis ) );memset ( pre, -1, sizeof ( pre ) );while ( ! q.empty() )q.pop();q.push( s );dis[s] = 0;vis[s] = 1;while ( ! q.empty() ) {int u = q.front();q.pop();vis[u] = 0;for ( int i = head[u];~ i;i = edge[i].next ) {int v = edge[i].v;if ( dis[v] > dis[u] + edge[i].w && edge[i].c > edge[i].flow ) {dis[v] = dis[u] + edge[i].w;pre[v] = i;if ( ! vis[v] ) {q.push( v );vis[v] = 1;}}}} return pre[t] != -1; }void MCMF ( int &maxflow, int &mincost ) {maxflow = mincost = 0;while ( spfa() ) {int MIN = INF;for ( int i = pre[t];~ i;i = pre[edge[i ^ 1].v] )MIN = min ( MIN, edge[i].c - edge[i].flow );for ( int i = pre[t];~ i;i = pre[edge[i ^ 1].v] ) {edge[i].flow += MIN;edge[i ^ 1].flow -= MIN;mincost += MIN * edge[i].w;}maxflow += MIN;} }int main() {while ( scanf ( "%d %d %d", &n, &m, &k ) != EOF ) {if ( n == 0 && m == 0 && k == 0 )return 0;int sum = 0;for ( int i = 1;i <= n;i ++ )for ( int j = 1;j <= k;j ++ ) {scanf ( "%d", &need[i][j] );sum += need[i][j];}for ( int i = 1;i <= m;i ++ )for ( int j = 1;j <= k;j ++ )scanf ( "%d", &num[i][j] );for ( int i = 1;i <= k;i ++ )for ( int j = 1;j <= n;j ++ )for ( int p = 1;p <= m;p ++ )scanf ( "%d", &matrix[i][j][p] );s = 0;t = n + m + 1;int result = 0, Flow = 0;for ( int i = 1;i <= k;i ++ ) {memset ( head, -1, sizeof ( head ) );cnt = 0;for ( int j = 1;j <= n;j ++ ) {add ( s, j, need[j][i], 0 );add ( j, s, 0, 0 );}for ( int j = 1;j <= n;j ++ )for ( int p = 1;p <= m;p ++ ) {add ( j, n + p, num[p][i], matrix[i][j][p] );add ( n + p, j, 0, -matrix[i][j][p] );}for ( int j = 1;j <= m;j ++ ) {add ( j + n, t, num[j][i], 0 );add ( t, j + n, 0, 0 );}int mincost, maxflow;MCMF ( maxflow, mincost );result += mincost;Flow += maxflow;}if ( Flow == sum )printf ( "%d\n", result );elseprintf ( "-1\n" );}return 0; }

T3：工作安排

你的公司接到了一批訂單。訂單要求你的公司提供n類產(chǎn)品，產(chǎn)品被編號為$1n$，其中第i類產(chǎn)品共需要Ci件。公司共有m名員工，員工被編號為$1m$員工能夠制造的產(chǎn)品種類有所區(qū)別。一件產(chǎn)品必須完整地由一名員工制造，不可以由某名員工制造一部分配件后，再轉(zhuǎn)交給另外一名員工繼續(xù)進(jìn)行制造。

我們用一個(gè)由0和1組成的m*n的矩陣A來描述每名員工能夠制造哪些產(chǎn)品。矩陣的行和列分別被編號為$1m$和$1n$，Ai,j為1表示員工i能夠制造產(chǎn)品j，為0表示員工i不能制造產(chǎn)品j。

如果公司分配了過多工作給一名員工，這名員工會變得不高興。我們用憤怒值來描述某名員工的心情狀態(tài)。憤怒值越高，表示這名員工心情越不爽，憤怒值越低，表示這名員工心情越愉快。員工的憤怒值與他被安排制造的產(chǎn)品數(shù)量存在某函數(shù)關(guān)系，鑒于員工們的承受能力不同，不同員工之間的函數(shù)關(guān)系也是有所區(qū)別的。

對于員工i，他的憤怒值與產(chǎn)品數(shù)量之間的函數(shù)是一個(gè)Si+1段的分段函數(shù)。當(dāng)他制造第$1Ti$,1件產(chǎn)品時(shí)，每件產(chǎn)品會使他的憤怒值增加Wi,1，當(dāng)他制造第$Ti,1+1Ti,2$件產(chǎn)品時(shí)，每件產(chǎn)品會使他的憤怒值增加$Wi,2\dots \dots$為描述方便，設(shè)$Ti,0=0,Ti,si+1=+\infty ，$那么當(dāng)他制造第$Ti,j?1+1Ti,j$件產(chǎn)品時(shí)，每件產(chǎn)品會使他的憤怒值增加$Wi,j，1\le j\le Si+1$。

你的任務(wù)是制定出一個(gè)產(chǎn)品的分配方案，使得訂單條件被滿足，并且所有員工的憤怒值之和最小。由于我們并不想使用Special Judge，也為了使選手有更多的時(shí)間研究其他兩道題目，你只需要輸出最小的憤怒值之和就可以了。

Input
第一行包含兩個(gè)正整數(shù)m和n，分別表示員工數(shù)量和產(chǎn)品的種類數(shù)；
第二行包含n 個(gè)正整數(shù)，第i個(gè)正整數(shù)為Ci；

以下m行每行n 個(gè)整數(shù)描述矩陣A；
下面m個(gè)部分，第i部分描述員工i的憤怒值與產(chǎn)品數(shù)量的函數(shù)關(guān)系。每一部分由三行組成：第一行為一個(gè)非負(fù)整數(shù)Si，第二行包含Si個(gè)正整數(shù)，其中第j個(gè)正整數(shù)為Ti,j，如果Si=0那么輸入將不會留空行（即這一部分只由兩行組成）。第三行包含Si+1個(gè)正整數(shù)，其中第j個(gè)正整數(shù)為Wi,j。

Output
僅輸出一個(gè)整數(shù)，表示最小的憤怒值之和。

Sample Input
2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6
Sample Output
24

Hint

題解

考語文啊~~

這道題的提示，保證了憤怒值是單調(diào)遞增的，就是費(fèi)用流的關(guān)鍵，給我們的解題提供了保障
我們考慮對于一堆產(chǎn)品，第一階段的產(chǎn)品生產(chǎn)的憤怒值一定小于后面階段的產(chǎn)品生產(chǎn)的憤怒值，那么我們把憤怒值當(dāng)成費(fèi)用，我們一定會先選擇第一階段的流量邊再選擇第二階段的流量邊，這樣就不會出現(xiàn)直接生產(chǎn)第二階段導(dǎo)致我們的出錯(cuò)

---

那么我們就建一個(gè)超級源點(diǎn)和超級匯點(diǎn)，源點(diǎn)和員工之間連邊，員工和產(chǎn)品之間連邊，邊數(shù)就是員工的憤怒階段$+1$，最后一段是$inf$，每個(gè)階段對應(yīng)的容量就是該階段的產(chǎn)品數(shù)，費(fèi)用就是憤怒值；最后是產(chǎn)品和匯點(diǎn)之間連邊

CODE

#include <queue> #include <cmath> #include <vector> #include <cstdio> #include <cstring> using namespace std; #define INF 1e9 #define LL long long #define MAXN 1005 struct node {int v, next;LL w, c, flow; }edge[MAXN * MAXN]; queue < int > q; int cnt, n, m, s, t; int head[MAXN], pre[MAXN], C[MAXN], a[MAXN][MAXN], b[MAXN]; bool vis[MAXN]; LL dis[MAXN];void add ( int x, int y, LL flow, LL cost ) {edge[cnt].next = head[x];edge[cnt].v = y;edge[cnt].w = cost;edge[cnt].c = flow;edge[cnt].flow = 0;head[x] = cnt ++; }bool spfa () {memset ( vis, 0, sizeof ( vis ) ); memset ( dis, 0x7f, sizeof ( dis ) );memset ( pre, -1, sizeof ( pre ) );while ( ! q.empty() )q.pop();q.push( s );dis[s] = 0;vis[s] = 1;while ( ! q.empty() ) {int u = q.front();q.pop();vis[u] = 0;for ( int i = head[u];~ i;i = edge[i].next ) {int v = edge[i].v;if ( dis[v] > dis[u] + edge[i].w && edge[i].c > edge[i].flow ) {dis[v] = dis[u] + edge[i].w;pre[v] = i;if ( ! vis[v] ) {q.push( v );vis[v] = 1;}}}} return pre[t] != -1; }void MCMF ( LL &maxflow, LL &mincost ) {maxflow = mincost = 0;while ( spfa() ) {LL MIN = INF;for ( int i = pre[t];~ i;i = pre[edge[i ^ 1].v] )MIN = min ( MIN, edge[i].c - edge[i].flow );for ( int i = pre[t];~ i;i = pre[edge[i ^ 1].v] ) {edge[i].flow += MIN;edge[i ^ 1].flow -= MIN;mincost += MIN * edge[i].w;}maxflow += MIN;} }int main() {memset ( head, -1, sizeof ( head ) );scanf ( "%d %d", &m, &n );s = 0;t = n + m + 1;for ( int i = 1;i <= n;i ++ ) {scanf ( "%d", &C[i] );add ( s, i, C[i], 0 );add ( i, s, 0, 0 );}for ( int i = 1;i <= m;i ++ )for ( int j = 1;j <= n;j ++ ) {scanf ( "%d", &a[i][j] );if ( a[i][j] ) {add ( j, i + n, INF, 0 );add ( i + n, j, 0, 0 );}}for ( int i = 1;i <= m;i ++ ) {int S;scanf ( "%d", &S );for ( int j = 1;j <= S;j ++ )scanf ( "%d", &b[j] );b[S + 1] = INF;for ( int j = 1;j <= S + 1;j ++ ) {int w;scanf ( "%d", &w );add ( i + n, t, ( b[j] - b[j - 1] ), w );add ( t, i + n, 0, -w );}}LL maxflow, mincost;MCMF ( maxflow, mincost );printf ( "%lld", mincost );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[费用流专题]Going Home，Minimum Cost，工作安排的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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