题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6214

Problem Description

Consider a network G=(V,E) with source s and sink t . An s-t cut is a partition of nodes set V into two parts such that s and t belong to different parts. The cut set is the subset of E with all edges connecting nodes in different parts. A minimum cut is the one whose cut set has the minimum summation of capacities. The size of a cut is the number of edges in the cut set. Please calculate the smallest size of all minimum cuts.

 

 

Input

The input contains several test cases and the first line is the total number of cases T (1≤T≤300) .
Each case describes a network G , and the first line contains two integers n (2≤n≤200) and m (0≤m≤1000) indicating the sizes of nodes and edges. All nodes in the network are labelled from 1 to n .
The second line contains two different integers s and t (1≤s,t≤n) corresponding to the source and sink.
Each of the next m lines contains three integers u,v and w (1≤w≤255) describing a directed edge from node u to v with capacity w .

 

 

Output

For each test case, output the smallest size of all minimum cuts in a line.

 

Sample Input
2
4 5
1 4
1 2 3
1 3 1
2 3 1
2 4 1
3 4 2
4 5
1 4
1 2 3
1 3 1
2 3 1
2 4 1
3 4 3
 

Sample Output
2
3

 

题目大意：给出T组测试数据，对于每组数据，给出n个点，m条边，起点s，终点t，输出s->t的 最小割 的 最小边数；

边权=边权*MOD+1，跑Dinic，最后ans=ans%MOD即为最小割的最小边数。

 

先来一个我的辣鸡代码，能A，但是时间是1000ms+（而且只能交C++）。

后来，我找到了原因！！我输入和输出的时候喜欢用cin和cout。。大佬们都用scanf，而且我还不喜欢加：

std::ios::sync_with_stdio(false);（加上这个之后G++1000ms+能A，但是我没换scanf，但应该会更快把）

所以有些时候就超时，所以，想更快的小伙伴们记得改成scanf，要不然可能会T。。。：

#include<math.h>  
#include<stdio.h>
#include<string.h>  

#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<fstream>
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 10000
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);

struct node{
	int v,w,nxt;
	node(int _v=0,int _w=0,int _nxt=0):
    v(_v),w(_w),nxt(_nxt){}
}edge[500005<<1];
int head[500005],cur[500005],ecnt;
int dis[500005];
int n,m,s,t;
void intt()
{
	clean(head,-1);
	clean(cur,-1);
	ecnt=0;
}
void add(int u,int v,int w)
{
	edge[ecnt]=node(v,w,head[u]);
	head[u]=ecnt++;
	edge[ecnt]=node(u,0,head[v]);
	head[v]=ecnt++;
}
/*---上面的是板子，不用动---*/
//扩展：HDU-3987 

bool bfs()
{
	clean(dis,-1);
	dis[s]=0;
	queue<int> que;
	que.push(s);
	while(que.size())
	{
		int u=que.front();
		que.pop();
		if(u==t)
			return 1;
		for(int i=head[u];i+1;i=edge[i].nxt)
		{
			int temp=edge[i].v;
			if(dis[temp]==-1&&edge[i].w>0)
			{
				dis[temp]=dis[u]+1;
				que.push(temp);
			}
		}
	}
	return 0;
}

int dfs(int u,int low)
{
	if(u==t||low==0)
		return low;
	int res=0;
	for(int &i=cur[u];i+1;i=edge[i].nxt)
	{
		int temp=edge[i].v;
		if(dis[temp]==dis[u]+1&&edge[i].w>0)
		{
			int f=dfs(temp,min(low-res,edge[i].w));
			edge[i].w-=f;
			edge[i^1].w+=f;
			res=res+f;
			if(res==low)
				break;
		}
	}
	return res;
}

void dinic()
{
	int ans=0;
	while(bfs())
	{
		memcpy(cur,head,sizeof(cur));
//		for(int i=0;i<=200;++i)
//			cur[i]=head[i];
		ans=ans+dfs(s,INF);
	}
	cout<<ans%mod<<endl;
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		intt();
		cin>>n>>m;
		cin>>s>>t;
		int a,b,l;
		for(int i=0;i<m;++i)
		{
			cin>>a>>b>>l;
			add(a,b,l*mod+1);
		}
		dinic();
	}
}