2019 杭电多校第一场 E HDU 6582 Path (最短路图上的最小割)

E HDU 6582 Path
使当前最短路 权值变了就行 同时坎的权值尽可能少
我们考虑求出最短路图 然后跑最小割
可以确定 d[v] == DJ.val[i] + d[u] 就是 最短路图上的边 加入网络流图中

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
typedef pair<ll, int> P;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, cas;

ll d[maxn];
struct GDJ{
	int head[maxn], cnt;
	int to[maxn << 1], nxt[maxn << 1];
	ll val[maxn << 1];
	
	void init(){
		memset(head, -1, (n + 5) * sizeof(int));
		cnt = -1;
	}
	
	void ade(int a, int b, ll c) {
		to[++cnt] = b;
		nxt[cnt] = head[a];
		val[cnt] = c;
		head[a] = cnt;
	}
	
	bool vis[maxn];
	void dj(){
		priority_queue<P, vector<P>, greater<P> > que;
		memset(d, 0x3f, (n + 5) * sizeof(ll));
		memset(vis, 0, (n + 5) * sizeof(bool));
		d[1] = 0;
		que.push(P(0, 1));
		while(!que.empty()){
			P p = que.top(); que.pop();
			int u = p.second;
			if(vis[u]) continue;
			vis[u] = 1;
			for(int i = head[u]; ~i; i = nxt[i]){
				int v = to[i];
				if(d[v] > d[u] + val[i]){
					d[v] = d[u] + val[i];
					que.push(P(d[v], v));
				}
			}
		}
	}
}DJ;

struct GDC{
	int depth[maxn], cur[maxn], head[maxn], cnt;
	int to[maxn << 1], nxt[maxn << 1];
	ll val[maxn << 1];
	
	void init(){
		memset(head, -1, (n + 5) * sizeof(ll));
		cnt = -1;
	}
	
	void ade(int a, int b, ll c) {
		to[++cnt] = b;
		nxt[cnt] = head[a];
		val[cnt] = c;
		head[a] = cnt;
	}
	
	bool bfs(){
		queue<int> que;
		que.push(1);
		memset(depth, 0, (n + 5) * sizeof(int));
		depth[1] = 1;
		while(!que.empty()){
			int u = que.front(); que.pop();
			for(int i = head[u]; ~i; i = nxt[i]) {
				if(val[i] > 0 && depth[to[i]] == 0) {
					depth[to[i]] = depth[u] + 1;
					que.push(to[i]);
				}
			}
		} 
		if(depth[n]) return 1;
		else return 0;
	}
	
	ll dfs(int u, ll dist){
		if(u == n) return dist;
		for(int &i = cur[u]; ~i; i = nxt[i]) {
			if(depth[to[i]] == depth[u] + 1 && val[i] > 0){
				ll tmp = dfs(to[i], min(dist, val[i]));
				if(tmp > 0) {
					val[i] -= tmp;
					val[i ^ 1] += tmp;
					return tmp;
				}
			}
		}
		return 0;
	}
	
	ll dinic() {
		ll res =0, d;
		while(bfs()){
			for(int i = 0; i <= n; i ++) cur[i] = head[i];
			while(d = dfs(1,INF)) res += d;
		}
		return res;
	}
}DC;

int main() {
	cin >> cas;
	while(cas --) {
		cin >> n >> m;
		DJ.init();
		for(int i = 1; i <= m; i++) {
			int a, b; ll c;
			cin >> a >> b >> c;
			DJ.ade(a, b, c);
		}
		
		DJ.dj();
	// cout << " " << d[n] << endl;
	// for(int i = 1; i <= n; i ++) cout << d[i] << endl;
		if(d[n] == INF) {
			cout << 0 << endl;
			continue;
		}
		DC.init();
		for(int u = 1; u <= n; u ++) {
			for(int i = DJ.head[u]; ~i; i = DJ.nxt[i]){
				int v = DJ.to[i];
				ll cst = DJ.val[i];
				if(d[v] == DJ.val[i] + d[u]){
				// cout << u << " " << v << endl;
					DC.ade(u, DJ.to[i], cst), DC.ade(DJ.to[i],u,0);
				}
			}
		}
		
		cout << DC.dinic() << endl;
	}
	return 0;
}