Dinic 80分求调
查看原帖
Dinic 80分求调
1308728
xsmfollower楼主2025/1/21 11:22

TLE #10,WA #13。

用的链式前向星建图,对着老师的代码写的,好像和题解区的建边方法有些不一样。

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define int long long
using namespace std;
const int N=1e4+10,M=1e5+10; int s,t,cnt=1,h[N],level[N];
struct Edge { int v,c,f,nxt; }e[M<<1];
void add(int u,int v,int w) { e[++cnt]=(Edge){v,w,0,h[u]},h[u]=cnt,e[++cnt]=(Edge){u,0,w,h[v]},h[v]=cnt; }
bool bfs() {
  memset(level,0,sizeof(level)),level[s]=1; queue<int>q; q.push(s);
  while(!q.empty()) {
  	int u=q.front(); q.pop();
  	for(int i=h[u];i;i=e[i].nxt) {
  	  int v=e[i].v,c=e[i].c,f=e[i].f;
  	  if(!level[v]&&c>f) level[v]=level[u]+1,q.push(v);
	}
  }
  return level[t];
}
int dfs(int u,int cp) {
  if(u==t) return cp;
  int t=cp;
  for(int i=h[u];i&&t;i=e[i].nxt) {
  	int v=e[i].v,c=e[i].c,f=e[i].f;
  	if(level[v]==level[u]+1&&c>f) {
  	  int k=dfs(v,min(t,c-f));
	  e[i].f+=k,e[i^1].f+=k,t-=k;
	}
  }
  return cp-t;
}
signed main() {
  int n,m,u,v,w; scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
  while(m--) scanf("%lld %lld %lld",&u,&v,&w),add(u,v,w);
  int sum=0;
  while(bfs()) sum+=dfs(s,2147483647);
  printf("%lld",sum);
  return 0;
}
2025/1/21 11:22
加载中...