天天看點
傳回

[網絡流]: 網絡流24題

1.配置設定問題

題目描述 Description

有n件工作要配置設定給n個人做。第i 個人做第j 件工作産生的效益為ij c 。試設計一個将

n件工作配置設定給n個人做的配置設定方案，使産生的總效益最大。

«程式設計任務：

對于給定的n件工作和n個人，計算最優配置設定方案和最差配置設定方案。

輸入描述 Input Description

第1 行有1 個正整數n，表示有n件工作要配置設定給n 個人做。接下來的n 行中，每行有n 個整數 cij ，1≤i≤n，1≤j≤n，表示第i 個人做第j件工作産生的效益為cij

輸出描述 Output Description

将計算出的最小總效益和最大總效益輸出

樣例輸入 Sample Input

5

2 2 2 1 2

2 3 1 2 4

2 0 1 1 1

2 3 4 3 3

3 2 1 2 1

樣例輸出 Sample Output

5

14

題解

此題比較簡單直接拆點 一連 跑最小費用就好 

求最大時可以寫個build函數(借鑒hwer寫法) 将邊權值變為負數 在重跑一邊最小費用 輸出-min_cost

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define inf 0x7ffffff
using namespace std;
int cnt=1,d[2005],head[2005],flag[2005],from[2005],start=0,end=2001,max_cost=0,mp[1005][1005],n;
struct edge{int to,next,flow,cost;}e[1000001];
void ini(int x,int y,int flow,int cost){e[++cnt].to=y;e[cnt].flow=flow;e[cnt].cost=cost;e[cnt].next=head[x];head[x]=cnt;}
void insert(int x,int y,int flow,int cost){ini(x,y,flow,cost);ini(y,x,0,-cost);}
queue<int>q;
bool spfa(){
	memset(d,127,sizeof(d));
	d[start]=0;q.push(start);flag[start]=1;
	while(!q.empty()){
		int k=q.front();q.pop();flag[k]=0;
		for(int i=head[k];i;i=e[i].next){
			int kk=e[i].to;
			if(e[i].flow>0&&d[kk]>d[k]+e[i].cost)
			{
				d[kk]=d[k]+e[i].cost;from[kk]=i;
				if(!flag[kk]){
					flag[kk]=1;
					q.push(kk);
				}
			}
		}
	}
	return d[end]<inf;
}
void mcf(){
	while(spfa())
	{
		max_cost+=d[end];
		for(int i=from[end];i;i=from[e[i^1].to])
		{
			e[i].flow-=1;e[i^1].flow+=1;
		}
	}
}
void build(int k){
    cnt=1;memset(head,0,sizeof(head));max_cost=0;
	for(int i=1;i<=n;i++)insert(start,i,1,0);
	for(int i=1;i<=n;i++)insert(i+n,end,1,0);
	for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            insert(i,j+n,1,k*mp[i][j]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&mp[i][j]);
	build(1);
	mcf();
	printf("%d\n",max_cost);
	build(-1);
	mcf();
	printf("%d\n",-max_cost);
	return 0;
}

2.負載平衡問題

題目描述 Description

G 公司有n 個沿鐵路運輸線環形排列的倉庫，每個倉庫存儲的貨物數量不等。如何用最

少搬運量可以使n 個倉庫的庫存數量相同。搬運貨物時，隻能在相鄰的倉庫之間搬運。

«程式設計任務：

對于給定的n 個環形排列的倉庫的庫存量，程式設計計算使n 個倉庫的庫存數量相同的最少

搬運量。

輸入描述 Input Description

第1 行中有1 個正整數n（n<=100），表示有n

個倉庫。第2 行中有n個正整數，表示n個倉庫的庫存量。

輸出描述 Output Description

将計算出的最少搬運量輸出

樣例輸入 Sample Input

5

17 9 14 16 4

樣例輸出 Sample Output

11

題解

每個點拆成xi,yi 先算平均數 源點連比平均數大的xi 彙點連比平均數小的yi(因為從xi運到yi) 把多貨的點和缺貨的分為兩個點去連圖

跑的時候從左到右跑 是以多貨的往少貨的運以下是網上的解釋

首先求出所有倉庫存貨量平均值，設第i個倉庫的盈餘量為A[i]，A[i] = 第i個倉庫原有存貨量 - 平均存貨量。建立二分圖，把每個倉庫抽象為兩個節點Xi和Yi。增設附加源S彙T。

1、如果A[i]>0，從S向Xi連一條容量為A[i]，費用為0的有向邊。

2、如果A[i]<0，從Yi向T連一條容量為-A[i]，費用為0的有向邊。

3、每個Xi向兩個相鄰頂點j，從Xi到Xj連接配接一條容量為無窮大，費用為1的有向邊，從Xi到Yj連接配接一條容量為無窮大，費用為1的有向邊。

求最小費用最大流，最小費用流值就是最少搬運量。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define inf 0x7ffffff
using namespace std;
struct edge{int to,next,flow,cost;}e[1000001];
int d[2005],head[2005],flag[2005],from[2005],cnt=1;int start=0,end=2001,min_cost=0,n,a[2005];
void ini(int x,int y,int flow,int cost){e[++cnt].to=y;e[cnt].flow=flow;e[cnt].cost=cost;e[cnt].next=head[x];head[x]=cnt;}
void insert(int x,int y,int flow,int cost){ini(x,y,flow,cost);ini(y,x,0,-cost);}
queue<int>q;
bool spfa(){
	memset(d,127,sizeof(d));
	d[start]=0;q.push(start);flag[start]=1;
	while(!q.empty()){
		int k=q.front();q.pop();flag[k]=0;
		for(int i=head[k];i;i=e[i].next){
			int kk=e[i].to;
			if(e[i].flow>0&&d[kk]>d[k]+e[i].cost)
			{
				d[kk]=d[k]+e[i].cost;from[kk]=i;
				if(!flag[kk]){
					flag[kk]=1;
					q.push(kk);
				}
			}
		}
	}
	return d[end]<inf;
}
void mcf(){
	while(spfa()){
		int mn=inf;
		for(int i=from[end];i;i=from[e[i^1].to])
			mn=min(mn,e[i].flow);
		min_cost+=d[end]*mn;
		for(int i=from[end];i;i=from[e[i^1].to])
		{
			e[i].flow-=mn;e[i^1].flow+=mn;
		}
	}
}
int main(){
	scanf("%d",&n);
	int tot=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		tot+=a[i];
	}
	tot/=n;
	for(int i=1;i<=n;i++)
		a[i]-=tot;
	for(int i=1;i<=n;i++){
		if(a[i]>0)	insert(start,i,a[i],0);
		else if(a[i]<0) insert(i+n,end,-a[i],0);
		int j=(i==1?n:i-1);
		insert(i,j,inf,1);insert(i,j+n,inf,1);
		j=(i==n?1:i+1);
		insert(i,j,inf,1);insert(i,j+n,inf,1);
	}
	mcf();
	printf("%d",min_cost);
	return 0;
}

3.飛行員配對問題

題目描述 Description

第二次世界大戰時期，英國皇家空軍從淪陷國征募了大量外籍飛行員。由皇家空軍派出的每一架飛機都需要配備在航行技能和語言上能互相配合的2 名飛行員，其中1 名是英國飛行員，另1 名是外籍飛行員。在衆多的飛行員中，每一名外籍飛行員都可以與其他若幹名英國飛行員很好地配合。如何選擇配對飛行的飛行員才能使一次派出最多的飛機。對于給定的外籍飛行員與英國飛行員的配合情況，試設計一個算法找出最佳飛行員配對方案，使皇家空軍一次能派出最多的飛機。

對于給定的外籍飛行員與英國飛行員的配合情況，程式設計找出一個最佳飛行員配對方案，使皇家空軍一次能派出最多的飛機。

輸入描述 Input Description

由檔案input.txt提供輸入資料。檔案第1 行有2個正整數m和n。n是皇家空軍的飛行員總數(n<100)；m是外籍飛行員數。外籍飛行員編号為1~m；英國飛行員編号為m+1~n。接下來每行有2 個正整數i和j，表示外籍飛行員i可以和英國飛行員j配合。檔案最後以2個-1 結束。

輸出描述 Output Description

程式運作結束時，将最佳飛行員配對方案輸出到檔案output.txt 中。第1 行是最佳飛行員配對方案一次能派出的最多的飛機數M。接下來M 行是最佳飛行員配對方案。每行有2個正整數i和j，表示在最佳飛行員配對方案中，飛行員i和飛行員j 配對。如果所求的最佳飛行員配對方案不存在，則輸出‘No Solution!’。

樣例輸入 Sample Input

10 5

1 7

2 6

2 10

3 7

4 8

5 9

樣例輸出 Sample Output

4

題解

就是一個裸的二分圖比對 可以用網絡流和二分圖比對兩種方法做 顯然二分圖比對更好打

二分圖：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m;
int flag[2005],mp[2005][2005],mat[2005];
bool km(int x){
	for(int i=m;i<=n;i++)
	{
		if(mp[x][i]&&!flag[i]){
			flag[i]=1;
			if(!mat[i]||km(mat[i])){
				mat[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
	scanf("%d%d",&m,&n);
	int x,y;
	while(scanf("%d%d",&x,&y)){
		if(x==-1&&y==-1) break;
		mp[x][y]=mp[y][x]=1;
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		memset(flag,0,sizeof(flag));
		if(km(i)) ans++;
	}
	if(ans==0)
	printf("No Solution!\n");
	else
	{
		printf("%d\n",ans);
		for(int i=m+1;i<=n;i++)
		{
			if(mat[i])
			printf("%d %d\n",mat[i],i);
		}
	}
	return 0;
}

網絡流：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#define inf 0x7ffffff
using namespace std;
int d[2005],head[2005],ans=0,cnt=1,n,m;
int start=0,end=2001;
struct edge{int to,next,flow;}e[100001];
queue<int>q;
void ini(int x,int y,int flow){
	e[++cnt].to=y;e[cnt].flow=flow;e[cnt].next=head[x];head[x]=cnt;
}
void insert(int x,int y,int flow){
	ini(x,y,flow);ini(y,x,0);
}
bool bfs(){
	memset(d,-1,sizeof(d));
	d[start]=0;
	q.push(start);
	while(!q.empty()){
		int k=q.front();q.pop();
		for(int i=head[k];i;i=e[i].next){
			int kk=e[i].to;
			if(d[kk]==-1&&e[i].flow>0){
				d[kk]=d[k]+1;
				q.push(kk);
			}
		}
	}
	return d[end]!=-1;
}
int dfs(int x,int f){
	if(x==end) return f;
	for(int i=head[x];i;i=e[i].next){
		int k=e[i].to;int a;
		if(d[k]==d[x]+1&&e[i].flow>0&&(a=dfs(k,min(e[i].flow,f))))
		{
			e[i].flow-=a;
			e[i^1].flow+=a;
			return a;
		}
	}
	return 0;
}
void dinic(){
	while(bfs()){
		int a;
		while(a=dfs(start,inf))
			ans+=a;
	}
}
int main(){
	scanf("%d%d",&m,&n);
	int x,y;
	for(int i=1;i<=m;i++) insert(start,i,1);
	for(int i=m+1;i<=n;i++) insert(i,end,1);
	while(scanf("%d%d",&x,&y)){
		if(x==-1&&y==-1) break;
		insert(x,y,1);
	}
	dinic();
	if(ans==0)
	printf("No Solution!\n");
	else
		printf("%d\n",ans);
	return 0;
}

4.餐巾計劃問題

題目描述 Description

一個餐廳在相繼的 N 天裡，每天需用的餐巾數不盡相同。假設第 i 天需要 ri塊餐巾(i=1，2，…，N)。餐廳可以購買新的餐巾，每塊餐巾的費用為 p 分；或者把舊餐巾送到快洗部，洗一塊需 m 天，其費用為 f 分；或者送到慢洗部，洗一塊需 n 天(n>m)，其費用為 s<f 分。

每天結束時，餐廳必須決定将多少塊髒的餐巾送到快洗部，多少塊餐巾送到慢洗部，以及多少塊儲存起來延期送洗。但是每天洗好的餐巾和購買的新餐巾數之和，要滿足當天的需求量。

試設計一個算法為餐廳合理地安排好 N 天中餐巾使用計劃，使總的花費最小。

程式設計找出一個最佳餐巾使用計劃.

輸入描述 Input Description

第 1 行有 6 個正整數 N,p,m,f,n,s。N 是要安排餐巾使用計劃的天數；p 是每塊新餐巾的費用；m 是快洗部洗一塊餐巾需用天數；f 是快洗部洗一塊餐巾需要的費用；n 是慢洗部洗一塊餐巾需用天數；s 是慢洗部洗一塊餐巾需要的費用。接下來的 N 行是餐廳在相繼的 N 天裡，每天需用的餐巾數。

輸出描述 Output Description

将餐廳在相繼的 N 天裡使用餐巾的最小總花費輸出

樣例輸入 Sample Input

3 10 2 3 3 2

5

6

7

樣例輸出 Sample Output

145

題解

二分圖的思想

把每個點分為:

今天用了要去洗的(i-day) 和 洗好了可以去用的(day+1-2*day)  然後就是連邊 分四種情況（還可以留到明天再洗 費用為0） 

注意細節就好了 跑最小費用最大流

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define inf 0x7ffffff
using namespace std;
int day,p,m,f,n,s;int start=0,end=2001,cnt=1;
int d[2005],flag[2005],head[2005],from[2005],min_cost=0;
struct edge{int to,next,flow,cost;}e[1000001];
queue<int>q;
void ini(int x,int y,int flow,int cost){e[++cnt].to=y;e[cnt].flow=flow;e[cnt].cost=cost;e[cnt].next=head[x];head[x]=cnt;}
void insert(int x,int y,int flow,int cost){ini(x,y,flow,cost);ini(y,x,0,-cost);}
bool spfa(){
	memset(d,127,sizeof(d));
	q.push(start);
	d[start]=0;flag[start]=1;
	while(!q.empty()){
		int k=q.front();q.pop();flag[k]=0;
		for(int i=head[k];i;i=e[i].next){
			int kk=e[i].to;
			if(e[i].flow>0&&d[kk]>d[k]+e[i].cost)
			{
				d[kk]=d[k]+e[i].cost;from[kk]=i;
				if(!flag[kk]){
					flag[kk]=1;
					q.push(kk);
				}
			}
		}
	}
	return d[end]<inf;
}
void mcf(){
	while(spfa())
	{
		int mn=inf;
		for(int i=from[end];i;i=from[e[i^1].to])
			mn=min(mn,e[i].flow);
		min_cost+=d[end]*mn;
		for(int i=from[end];i;i=from[e[i^1].to])
		{
			e[i].flow-=mn;e[i^1].flow+=mn;
		}
	}
}
int main(){
	scanf("%d%d%d%d%d%d",&day,&p,&m,&f,&n,&s);
	for(int i=1;i<=day;i++){
		int x;
		scanf("%d",&x);
		insert(start,i,x,0);
		insert(i+day,end,x,0);
	}
	for(int i=1;i<=day;i++)
	{
		if(i+1<=day)	insert(i,i+1,inf,0);
		if(i+m<=day)	insert(i,i+m+day,inf,f);
		if(i+n<=day)	insert(i,i+n+day,inf,s);
		insert(start,day+i,inf,p);
	}
	mcf();
	printf("%d",min_cost);
	return 0;	
}

5.運輸問題

題目描述 Description

W 公司有m個倉庫和n 個零售商店。第i 個倉庫有ai 個機關的貨物；第j 個零售商店

需要bj個機關的貨物。貨物供需平衡，即  sum(si）=sum(bj)

。從第i 個倉庫運送每機關貨物到

第j 個零售商店的費用為cij 。試設計一個将倉庫中所有貨物運送到零售商店的運輸方案，

使總運輸費用最少。

程式設計任務：

對于給定的m 個倉庫和n 個零售商店間運送貨物的費用，計算最優運輸方案和最差運輸方案。

輸入描述 Input Description

的第1行有2 個正整數m和n，分别表示倉庫數和

零售商店數。接下來的一行中有m個正整數ai ，1≤i≤m，表示第i個倉庫有ai 個機關的貨

物。再接下來的一行中有n個正整數bj ，1≤j≤n，表示第j個零售商店需要bj 個機關的貨

物。接下來的m行，每行有n個整數，表示從第i 個倉庫運送每機關貨物到第j個零售商店

的費用cij 。

輸出描述 Output Description

将計算出的最少運輸費用和最多運輸費用輸出

樣例輸入 Sample Input

2 3

220 280

170 120 210

77 39 105

150 186 122

樣例輸出 Sample Output

48500

69140

題解

比較簡單就不說了 就是費用流裸題

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define inf 0x7ffffff
using namespace std;
int n,m;int start=0,end=2001,cnt=1;
int d[2005],c[2005][2005],a[2005],b[2005],flag[2005],head[2005],from[2005],min_cost;
struct edge{int to,next,flow,cost;}e[1000001];
queue<int>q;
void ini(int x,int y,int flow,int cost){e[++cnt].to=y;e[cnt].flow=flow;e[cnt].cost=cost;e[cnt].next=head[x];head[x]=cnt;}
void insert(int x,int y,int flow,int cost){ini(x,y,flow,cost);ini(y,x,0,-cost);}
bool spfa(){
	memset(d,127,sizeof(d));
	q.push(start);
	d[start]=0;flag[start]=1;
	while(!q.empty()){
		int k=q.front();q.pop();flag[k]=0;
		for(int i=head[k];i;i=e[i].next){
			int kk=e[i].to;
			if(e[i].flow>0&&d[kk]>d[k]+e[i].cost)
			{
				d[kk]=d[k]+e[i].cost;from[kk]=i;
				if(!flag[kk]){
					flag[kk]=1;
					q.push(kk);
				}
			}
		}
	}
	return d[end]<inf;
}
void mcf(){
	while(spfa())
	{
		int mn=inf;
		for(int i=from[end];i;i=from[e[i^1].to])
			mn=min(mn,e[i].flow);
		min_cost+=d[end]*mn;
		for(int i=from[end];i;i=from[e[i^1].to])
		{
			e[i].flow-=mn;e[i^1].flow+=mn;
		}
	}
}
void build(int k){
	cnt=1;
	memset(head,0,sizeof(head));
	for(int i=1;i<=m;i++) insert(start,i,a[i],0);
	for(int i=1;i<=n;i++) insert(i+m,end,b[i],0);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			insert(i,j+m,inf,k*c[i][j]);
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&c[i][j]);
	build(1);
	mcf();printf("%d\n",min_cost);
	min_cost=0;
	build(-1);
	mcf();printf("%d\n",-min_cost);
	return 0;
}

6.太空飛行計劃問題

Description

W教授正在為國家航天中心計劃一系列的太空飛行。每次太空飛行可進行一系列商業性實驗而擷取利潤。現已确定了一個可供選擇的實驗集合 E={E1，E2，…，Em}，和進行這些實驗需要使用的全部儀器的集合 I={I1，I2，…In}。實驗 Ej需要用到的儀器是 I的子集。配置儀器 Ik的費用為 ck美元。實驗 Ej的贊助商已同意為該實驗結果支付 pj美元。W教授的任務是找出一個有效算法，确定在一次太空飛行中要進行哪些實驗并是以而配置哪些儀器才能使太空飛行的淨收益最大。這裡淨收益是指進行實驗所獲得的全部收入與配置儀器的全部費用的差額。

對于給定的實驗和儀器配置情況，程式設計找出淨收益最大的試驗計劃。

Input

檔案第 1行有 2個正整數 m和 n。m是實驗數，n是儀器數。

接下來的 m行，每行是一個實驗的有關資料。第一個數贊助商同意支付該實驗的費用；接着是該實驗需要用到的若幹儀器的編号。

最後一行的 n個數是配置每個儀器的費用。

Output

程式運作結束時，将最佳實驗方案輸出。第 1行是實驗編号；第 2行是儀器編号；最後一行是淨收益。

Sample Input 

2 3
10 1 2
25 2 3
5 6 7

Sample Output 

1 2
1 2 3
17

HINT 

n,m < 50

題解

有點難。。但是建好圖就簡單了 轉換為最小割 進而轉為最大流

下面是解析：

【問題分析】

最大權閉合圖問題，可以轉化成最小割問題，進而用最大流解決。

【模組化方法】

把每個實驗看作二分圖X集合中的頂點，每個裝置看作二分圖Y集合中的頂點，增加源S和彙T。

1、從S向每個Xi連接配接一條容量為該點收入的有向邊。

2、從Yi向T連接配接一條容量為該點支出的有向邊。

3、如果一個實驗i需要裝置j，連接配接一條從Xi到Yj容量為無窮大的有向邊。

統計出所有實驗的收入隻和Total，求網絡最大流Maxflow，最大收益就是Total-Maxflow。對應的解就是最小割劃分出的S集合中的點，也就是最後一次增廣找到阻塞流時能從S通路到的頂點。

【模組化分析】

定義一個割劃分出的S集合為一個解，那麼割集的容量之和就是(未被選的A集合中的頂點的權值 + 被選的B集合中的頂點的權值)，記為Cut。

A集合中所有頂點的權值之和記為Total，那麼Total - Cut就是(被選的A集合中的頂點的權值 - 被選的B集合中的頂點的權值)，即為我們的目标函數，記為A。

要想最大化目标函數A，就要盡可能使Cut小，Total是固定值，是以目标函數A取得最大值的時候，Cut最小，即為最小割。

該問題的一般模型為最大權閉合圖，相關讨論見《最小割模型在資訊學競賽中的應用》作者胡伯濤。

大概就是這樣了。。下面代碼：

//最小割——>最大流
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define inf 0x7ffffff
using namespace std;
int n,m,cnt=1;
int w[2005],cost[2005],d[2005],head[2005],start=0,end=2001,ans=0;
struct edge{int to,next,flow;}e[100001];
void ini(int x,int y,int flow){
	e[++cnt].to=y;e[cnt].flow=flow;e[cnt].next=head[x];head[x]=cnt;
}
void insert(int x,int y,int flow){
	ini(x,y,flow);ini(y,x,0);
}
queue<int>q;
bool bfs(){
	memset(d,-1,sizeof(d));
	q.push(start);d[start]=0;
	while(!q.empty()){
		int k=q.front();q.pop();
		for(int i=head[k];i;i=e[i].next){
			int kk=e[i].to;
			if(e[i].flow>0&&d[kk]==-1)
			{
				d[kk]=d[k]+1;
				q.push(kk);
			}
		}
	}
	return d[end]!=-1;
}
int dfs(int x,int f){
	if(x==end) return f;
	for(int i=head[x];i;i=e[i].next){
		int k=e[i].to;int a;
		if(d[k]==d[x]+1&&e[i].flow>0&&(a=dfs(k,min(e[i].flow,f))))
		{
			e[i].flow-=a;
			e[i^1].flow+=a;
			return a;
		}
	}
	return 0;
}
void dinic(){
	while(bfs()){
		int a;
		while(a=dfs(start,end))
			ans+=a;
	}
}
int main(){
	int tot=0;
	scanf("%d%d",&m,&n);
	int tmp;
	for(int i=1;i<=m;i++){
		scanf("%d",&tmp);
		tot+=tmp;
		insert(start,i,tmp);
		char ch;
		int x=0;
		while(scanf("%c",&ch)){
			if(ch==' '){
				insert(i,x+1000,inf);
				x=0;
				continue;
			}
			else if(ch==10||ch==13){
                insert(i,x+1000,inf);
                x=0;break;
			}
			else
				x=x*10+ch-'0';
		}
	}
	int x;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		insert(i+1000,end,x);
	}
	dinic();
	printf("%d",tot-ans);
	return 0;
}
網絡流 最大流 費用流 最小割
上一篇: Windows7安裝JDK設定環境變量
下一篇: 跨境汽配大賣的庫存之痛，周而複始的降庫存運動最近讓好多...

繼續閱讀