hdu4280网络流之dinic

时间:2021-06-19 15:44:37

这题就是个模板题,不过我是第一次写dinic,好久没用链式前向星又不会了。。。

时间:9126ms

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=,inf=; struct edge{
int to,cap,next;
}e[N<<];
int s,t,cnt;
int dis[N],cur[N];
int head[N];
void add(int u,int v,int c)//链式前向星
{
e[cnt].to=v;
e[cnt].cap=c;
e[cnt].next=head[u];
head[u]=cnt++;
}
bool bfs()
{
memset(dis,-,sizeof dis);
dis[s]=;
queue<int>q;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i!=-;i=e[i].next)//与x相连的所有点
{
int temp=e[i].to;
if(dis[temp]==-&&e[i].cap>)//这一条边还有增广的可能
{
dis[temp]=dis[x]+;
q.push(temp);
}
}
}
return dis[t]>-;//找到增广路
}
int dfs(int x,int cap)
{
if(x==t)return cap;
int flow=;
for(int i=head[x];i!=-;i=e[i].next)
{
int temp=e[i].to;
if(dis[temp]==dis[x]+&&e[i].cap)
{
int f=dfs(temp,min(cap-flow,e[i].cap));
e[i].cap-=f;//正向边
e[i^].cap+=f;//反向边
flow+=f;
if(flow==cap)break;
}
}
if(!flow)dis[x]=-;//不加会超时
return flow;
}
int max_flow()
{
int flow=,f;
while(bfs()){//还有增广路
while((f=dfs(s,inf))>)flow+=f;//进行多路增广
}
return flow;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int k,n,m;
cin>>k;
while(k--){
cin>>n>>m;
int smin=inf,tmax=-inf;
s=t=;
int a,b,c;
for(int i=;i<=n;i++)
{
cin>>a>>b;
if(a<=smin)smin=a,s=i;
if(a>=tmax)tmax=a,t=i;
}
cnt=;
memset(head,-,sizeof head);
while(m--){
cin>>a>>b>>c;
add(a,b,c);//正向边
add(b,a,c);//反向边
}
int ans=max_flow();
cout<<ans<<endl;
}
return ;
}