HDU 3549 Flow Problem(有向边网络流) - c++编程基础

题意：T个测试数据

下面n，m表示n个点m条有向带权边

m条边

问：从1-n最大流多少

测板子的题目，没啥思路

下面用的是dinic，开始没有考虑反向弧debug了好久，附赠一大坨测试数据

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 100000000
#define eps 1e-8
#define N 205
#define M 1050
#define ll int
using namespace std;
inline ll Max(ll a,ll b){return a>b a:b;}
inline ll Min(ll a,ll b){return aQ;	while(!Q.empty())Q.pop();
	Q.push(Start);	dis[Start]=0;	vis[Start]=1;
	while(!Q.empty())
	{
		int u = Q.front(); Q.pop();
		for(int i=head[u];i!=-1;i=edge[i].nex){
			Edge E =edge[i];
			if(!vis[E.to] && E.cap>E.flow)
			{
				vis[E.to]=1;
				dis[E.to]=dis[u]+1;
				if(E.to==End)return true;
				Q.push(E.to);
			}
		}
	}
	return false;
}
int DFS(int x, int a,int End){//流入x 的流量是a
	if(x==End || a==0)return a;
	int flow = 0, f;
	for(int& i=cur[x];i!=-1;i=edge[i].nex)
	{
		Edge& E = edge[i];
		if(dis[x]+1 == dis[E.to] && (f = DFS(E.to , Min(a, E.cap-E.flow), End))>




0 )
		{
			E.flow += f;
			edge[ i^1 ].flow -= f;//反向边要减掉
			flow += f;
			a -= f;
			if(a==0)break;
		}
	}
	return flow;
}
int Maxflow(int Start,int End){
	int flow=0; 
	while(BFS(Start,End)){
		memcpy(cur,head,sizeof(head));//把head的数组复制过去
		flow += DFS(Start, inf, End);
	}
	return flow;
}
int main() {
	int T,Cas=1,n,m,i,a,b,c;scanf("%d",&T);
	while (T--) {
		memset(head,-1,sizeof(head));
		edgenum=0;
		scanf("%d %d",&n,&m);		
		while(m--)
		{
			scanf("%d %d %d",&a,&b,&c);
			addedge(a,b,c);
		}
		printf("Case %d: %d\n",Cas++,Maxflow(1,n));
	}
	return 0;
}

/*
99
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1

3 2
1 3 2
1 3 5

3 2
1 2 456
1 2 56431

3 3 
1 3 100
1 1 100
1 1 100

11 15
1 2 1 
1 3 1
1 4 1
2 5 1
2 6 1
3 7 1
3 8 1
4 9 1
4 10 1
5 11 1
6 11 1
7 11 1
8 11 1
9 11 1
10 11 1

11 15
1 2 2
1 3 2
1 4 2
2 5 1
2 6 1
3 7 1
3 8 1
4 9 1
4 10 1
5 11 1
6 11 1
7 11 1
8 11 1
9 11 1
10 11 1

11 15
1 2 2
1 3 1
1 4 2
2 5 1
2 6 1
3 7 1
3 8 1
4 9 1
4 10 1
5 11 1
6 11 1
7 11 1
8 11 1
9 11 1
10 11 1

2 0

2 1
1 2 4651

4 4
1 2 10
2 1 5
2 4 20
1 3 3

4 5
1 2 10
2 1 5
2 4 20
1 3 3
3 4 1

9 10
1 5 2
2 4 6
2 3 4 
1 2 9
3 9 5
5 9 4
2 3 1
4 2 1
6 7 1
3 7 2

4 4
1 2 10
1 3 2
3 4 1
2 4 1

4 4
1 2 1
1 3 1
3 4 10
2 4 10

ans:
1
2
7
0
100
3
6
5
0
4651
10
11
7
2
2

*/