[SHOI2010]最小生成树

输入文件的第一行有3个正整数n、m、Lab分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。
接下来m行依次描述标号为1,2,3…m的无向边，每行描述一条边。每个描述包含3个整数x、y、d，表示这条边连接着标号为x、y的点，且这条边的权值为d。
输入文件保证1<=x,y<=N,x不等于y,且输入数据保证这个无向图一定是一个连通图。

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2020-09-30 20:20:09

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=505,M=1605,Inf=1e9;
struct Graph{int u,v,w;}g[M];
struct Edge{int to,f,nxt;}e[M];
int n,m,lab,s,t,fst[N],nf[N],tote,lev[N],q[N],hd,tl;
void adde(int u,int v,int f){
	e[++tote]=(Edge){v,f,fst[u]};fst[u]=tote;
	e[++tote]=(Edge){u,f,fst[v]};fst[v]=tote;
}
bool bfs(){
	memset(lev,-1,sizeof(lev));
	lev[s]=0;q[hd=tl=1]=s;
	while(hd<=tl){
		int u=q[hd++];
		for(int i=fst[u],v;~i;i=e[i].nxt)if(lev[v=e[i].to]<0&&e[i].f)
			lev[v]=lev[u]+1,q[++tl]=v;
	}
	return lev[t]>=0; 
}
int dfs(int u,int lim){
	if(u==t)return lim;
	int res=0;
	for(int i=nf[u],v,f;~i;i=e[i].nxt){
		v=e[i].to;f=e[i].f;
		if(lev[v]==lev[u]+1&&f){
			int tmp=dfs(v,min(lim,f));
			e[i].f-=tmp;e[i^1].f+=tmp;lim-=tmp;res+=tmp;
			if(!lim){nf[u]=i;return res;}
		}
	}
	nf[u]=-1;return res;
}
int maxflow(){
	int res=0;
	while(bfs())memcpy(nf,fst,sizeof(nf)),res+=dfs(s,Inf);
	return res;
}
int main(){
	memset(fst,-1,sizeof(fst));tote=1;
	scanf("%d%d%d",&n,&m,&lab);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w);
	s=g[lab].u;t=g[lab].v;
	for(int i=1;i<=m;i++)if(i!=lab&&g[i].w<=g[lab].w)adde(g[i].u,g[i].v,g[lab].w-g[i].w+1);
	printf("%d\n",maxflow());
	return 0;
}

详情