萌新在线求助TLE:仅差一个点AC
查看原帖
萌新在线求助TLE:仅差一个点AC
118000
returnG楼主2020/7/9 16:38

只有#9TLE掉了,用的dinic+弧优化,用的vector存边,还愿大佬赐教。

91分代码:

#include <bits/stdc++.h>
using namespace std;
long long n,m,s,t,ans=0;
long long minnn;
long long d[205];
vector<long long> ed[205];
struct edge{
	long long u;
	long long v;
	long long w;
}e[100005];
int cur[100005];
bool bfs(){
	bool flag=0;
	memset(d,0,sizeof(d));
	memset(cur,0,sizeof(cur));
	queue<long long> q;
	q.push(s);
	d[s]=1;
	while(!q.empty()){
		long long u=q.front();
		q.pop();
		for(long long i=0;i<ed[u].size();i++){
			long long v=e[ed[u][i]].v,w=e[ed[u][i]].w;
			if(d[v])continue;
			if(w<=0)continue;
			d[v]=d[u]+1;
			q.push(v);
			if(v==t)flag=1;
		}
	}
	return flag;
}
long long dfs(long long u,long long minn){
	//cout<<u<<endl;
	if(u==t)return minn;
	long long k,rest=minn;
	for(long long i=cur[u];i<ed[u].size();i++){
		cur[u]=i;
		long long v=e[ed[u][i]].v,w=e[ed[u][i]].w;
		if(d[v]!=d[u]+1)continue;
		if(w<=0)continue;
		if(w)k=dfs(v,min(rest,w));
		if(!k)d[v]=0;
		e[ed[u][i]].w-=k;
		e[ed[u][i]^1].w+=k;
		rest-=k;
	}
	return minn-rest;
}
int main() {
	std::ios::sync_with_stdio(0);
	cin>>n>>m>>s>>t;
	for(long long i=0;i<m;i++){
		long long u,v,w;
		cin>>u>>v>>w;
		e[i*2].u=u;
		e[i*2].v=v;
		e[i*2].w=w;
		e[i*2+1].u=v;
		e[i*2+1].v=u;
		e[i*2+1].w=0;
		ed[u].push_back(i*2);
		ed[v].push_back(i*2+1);
	}
	while(bfs()){
		//for(long long i=1;i<=n;i++)cout<<d[i]<<' ';
		//cout<<endl;
		ans+=dfs(s,99999999);
		//cout<<ans<<endl;
	}
	cout<<ans;
	return 0;
}
2020/7/9 16:38
加载中...