为什么这个费用流代码结果恰好是答案的两倍
  • 板块学术版
  • 楼主PLDIS
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/14 22:02
  • 上次更新2023/11/3 03:45:28
查看原帖
为什么这个费用流代码结果恰好是答案的两倍
302356
PLDIS楼主2023/8/14 22:02

RT,本蒟蒻不理解这坨屎山发生了什么

P.S.:因为费用流板子题还询问别的,所以就不放那里了,请放过这个蒟蒻

class Min_Cost_Flow_Graph{

private:
	struct Flow_Edge{
		int v, cap, cost, id;
	};
	vector<Flow_Edge> gv[501];
	int n, tot;
	int curr[501], dis[501], vis[501], flow[30001], mp[30001];
	int source, sink;
public:
	void add_edge(int u, int v, int w, int x){
		Flow_Edge k; k.v = v, k.cap = w, k.cost = x, k.id = ++tot;
		gv[u].pb(k); mp[tot] = gv[u].size() - 1;
		flow[tot] = w;
		k.v = u, k.cap = 0LL, k.cost = -x, k.id = ++tot;
		gv[v].pb(k); mp[tot] = gv[v].size() - 1;
		flow[tot] = 0LL;
	}
	void init(int k, int sc, int sk){
		n = k, source = sc, sink = sk;
		rep(i, 1, n, 1)
			gv[i].clear(), curr[i] = 0LL, mp[i] = 0LL;
		tot = -1;
	}
	bool spfa(){
		rep(i, 1, n, 1)
			vis[i] = 0LL, dis[i] = MAXN;
		qi q; q.push(source);
		dis[source] = 0LL;
		while(!q.empty()){
			int x = q.front(); q.pop();
			vis[x] = 0;
			repn(i, 0, gv[x].size(), 1){
				Flow_Edge u = gv[x][i];
				int y = u.v, z = u.cost;
				if(u.cap > 0 && dis[y] > dis[x] + z){
					dis[y] = dis[x] + z;
					if(!vis[y])
						vis[y] = 1, q.push(y);
				}
			}
		}
		return (dis[sink] <= INT_MAX);
	}
	int dfs(int x, int fl){
		if(x == sink) return fl;
		int ans = 0;
		vis[x] = 1;
		int i = curr[x];
		while(i < gv[x].size()){
			curr[x] = i;
			Flow_Edge y = gv[x][i];
			i++; int tmp;
			if(y.cap <= 0 || dis[y.v] != dis[x] + y.cost || vis[y.v]){
				continue;
			}
			if((tmp = dfs(y.v, min(fl - ans, y.cap))) > 0){
				gv[x][mp[y.id]].cap -= tmp;
				gv[y.v][mp[y.id ^ 1]].cap += tmp;
				ans += tmp;
			}
			if(ans >= fl) break;
		}
		return ans;
	}
	int Min_Cost_Max_Flow(){
		int fl; int ans = 0;
		while(spfa()){
			rep(i, 1, n, 1) curr[i] = 0LL;
			while(1){
				int fl = dfs(source, MAXN);
				if(fl == 0) break;
				rep(i, 1, n, 1) vis[i] = 0LL;
			}
		}
		rep(i, 1, n, 1){
			repn(j, 0, gv[i].size(), 1){
				Flow_Edge x = gv[i][j];
				ans += x.cost * (flow[x.id] - x.cap);
			}
		}
		return ans;
	}
};
2023/8/14 22:02
加载中...