求助ISAP
  • 板块题目总版
  • 楼主__mcx_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/23 22:12
  • 上次更新2023/11/2 18:25:27
查看原帖
求助ISAP
308439
__mcx_楼主2023/9/23 22:12

RT,刚学,仿着dinic写的,不懂为什么一直错。求教

#include<bits/stdc++.h>
#define ll long long 
#define rep(i,a,b) for(int i = a;i <= b;i ++)
#define per(i,a,b) for(int i = b;i >= a;i --)

using namespace std;

const int mm = 1e4+10;
const int nn = 5e2+10;
const ll inf = 1e18;
struct edge
{
	ll v,nt,w,fl;
}e[mm<<1];

int ecnt,h[nn],cur[nn];
void add(ll u,ll v,ll w)
{
	e[++ecnt] = {v,h[u],w,0};
	h[u] = ecnt;
}
int hs(int x)
{
	int tmp = x & 1 ? 1 : -1;
	return x + tmp;
}

int dep[nn],gap[nn];

int S,T,n,m;
void bfs()
{	
	queue<int> q;
	rep(i,1,n) dep[i] = -1;
//	dep[T] = 1;gap[1] = 1;
	dep[T] = 0;gap[0] = 1;
	q.push(T);
	while(!q.empty())
	{
		int x = q.front();q.pop();
		for(int i = h[x];i;i = e[i].nt)
		{
			int y = e[i].v;
			if(dep[y] != -1) continue;
			q.push(y);
//			cout << y << " " << x << "\n";
			dep[y] = dep[x] + 1;
			gap[dep[y]]++; 
		}
	}
//	rep(i,1,n) cout << dep[i] << " ";cout << "\n";
//    rep(i,1,n) cout << gap[i] << " ";cout << "\n";
}
ll ans,max_flow;
ll dfs(int x,ll flow)
{
	if(x == T || flow == 0)
	{
		ans += flow;
		return flow;	
	}
	ll ret = 0;
	for(int i = h[x];i;i = e[i].nt)
	{
		int y = e[i].v;
		ll tmp = 0;
		if((e[i].w - e[i].fl > 0)&&( tmp = dfs(y,min(flow - ret,e[i].w - e[i].fl))) && dep[y] + 1 == dep[x])
		{
			e[i].fl += tmp;
			e[hs(i)].fl -= tmp;
			ret += tmp;
			if(ret == flow) return ret; 
		}
	}
//	cout << x << " " << T << " " << ret << "\n";
	--gap[dep[x]];
	if(!gap[dep[x]]) dep[S] = n + 1;
	dep[x] ++;
	gap[dep[x]] ++;
	return ret;
}
void ISAP()
{
	bfs();
//	rep(i,1,n) cout << "dep:" << dep[i] << " " << i << "\n";
	int time = 0;
	while(dep[S] < n) dfs(S,inf);
//	cout <<"time:" << ++time << "\n";
	cout << ans << "\n"; 
}
void mian()
{
	cin >> n >> m >> S >> T;
	int x,y;ll z;
	rep(i,1,m) cin >> x >> y >> z,add(x,y,z),add(y,x,0);
	ISAP();
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0); 
//	rep(i,1,5) cout << i << hs(i) << "\n";
	mian();
	return 0;
}
2023/9/23 22:12
加载中...