HDU6582(最短路+最小割)

Hdu6582

思路比較簡單，先找最短路，然後跑dinic求最小割，一開始還想再建圖，後面看了别人的代碼，其實隻要把不是最短路徑上的路徑的權值歸零就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e17;
const int maxn = 2e6+50;
int n,m;
int T;
int ecnt=1,head[maxn];
struct node
{
	int v,nxt;
	ll w;
}e[maxn];
inline void add(int u,int v,ll w){
	e[++ecnt].v=v;
	e[ecnt].w=w;
	e[ecnt].nxt=head[u];
	head[u]=ecnt;
}
ll dis[maxn];
bool vis[maxn];
void spfa(int s){
	for(int i=1;i<=n;i++)dis[i]=inf;
	memset(vis,false,sizeof(vis));
	dis[s]=0;
	queue<int>q;
	q.push(s);
	vis[s]=1;
	while (!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(e[i].w>0&&dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
}
ll dep[maxn],inque[maxn],vi,cur[maxn];
int s,t;
ll maxflow=0;
ll mi(int a,ll b){
	return a<b?a:b;
}
bool bfs(){
    for(register int i=0;i<=t;i++)
        cur[i]=head[i],dep[i]=0x3f3f3f3f,inque[i]=0;
    //兩個memset一個memcpy還不如直接循環
    dep[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int d=e[i].v;
            if(dep[d]>dep[u]+1&&e[i].w){
                dep[d]=dep[u]+1;//注意與EK的差別
                if(inque[d]==0){
                    q.push(d);
                    inque[d]=1;
                }
            }
        }
    }
    if(dep[t]!=0x3f3f3f3f)return 1;
    return 0;
}//給增廣路上的點分層
ll dfs(int u,int flow){
	ll rlow=0;
    if(u==t){
        vi=1;//可以到達t
        maxflow+=flow;//其實可以直接在這裡累加最大流
        return flow;
    }
	ll used=0;//該點已經使用的流量
    for(int i=cur[u];i;i=e[i].nxt){
        cur[u]=i;//修改目前弧
        int d=e[i].v;
		if(e[i].w&&dep[d]==dep[u]+1){
			if(rlow=dfs(d,mi(flow-used,e[i].w))){
                used+=rlow;
				e[i].w-=rlow;
				e[i^1].w+=rlow;
                if(used==flow)break;
            }
        }
    }
    return used;//傳回該點已使用流量lailei renhe
}//尋找增廣路
ll Dinic(){
    while(bfs()){
        vi=1;
        while(vi==1){
            vi=0;
            dfs(s,inf);
        }
    }
    return maxflow;
}//Dinic尋找最大流
int main(){
	scanf("%d",&T);
	while (T--)
	{
		memset(head,0,sizeof(head));
		memset(e,0,sizeof(e));
		maxflow=0;
		ecnt=1;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			int u,v;
			ll w;
			scanf("%d%d%lld",&u,&v,&w);
			add(u,v,w);
			add(v,u,0); //建好雙向邊  跑dinic的時候用
		}
		spfa(1);
		for(int i=1;i<=n;i++){
			for(int j=head[i];j;j=e[j].nxt){
				if(dis[e[j].v]!=dis[i]+e[j].w)
					e[j].w=0;      //非最短路徑上的邊的權值清零
			}
		}
		s=1;
		t=n;
		printf("%lld\n",Dinic());
	}
	return 0;
}