hdu 6582 Path【最短路】【最小割】【2019 Multi-University Training Contest 1】

题意:

给你一个n个点，m条边的有向图。让你以最小的代价删除一些边使得从点1到点n的最短路变长，删掉一条边的代价为这条边的长度，不用考虑删完之后点1是否能到达点n。

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6582

题解：

要使最短路变长，那么我们就要删掉最短路的边，我们可以知道点1到点n也许不止一条最短路，那么这些最短路可以构成一个有向无环图(DAG)，我们要以最小代价破坏这个有方向,就是求这个图的最小割。

怎么判断这条边属不属于最短路呢，首先用Dijkstra算法求出 源点到终点的最短路。然后分别求出源点到每个点的最短距离 lowcost[0][i]  和 每个点到 终点的最短距离 lowcost[1][v] ， 如果 lowcost[0][u]  + w(u, v) + lowcost[1][v] ==   lowcost[0][n](源点到终点的最短路), 则边w(u, v)属于最短路。

AC_code:

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const double eps = 1e-9;
const ll inf = 10e15;
const int mod = 123456789;
const int maxn = 10000+10;

struct Edge {
	ll from,to,cap,flow;
	Edge(ll u,ll v,ll c,ll f): from(u),to(v),cap(c),flow(f) {}
};

struct EdmondsKarp {
	ll n,m;
	vector<Edge> edges;
	vector<ll> G[maxn];
	ll a[maxn];
	ll p[maxn];

	void init(ll n) {
		for(ll i=0; i<n; i++) G[i].clear();
		edges.clear();
	}

	void AddEdge(ll from,ll to,ll cap) {
		edges.push_back(Edge(from,to,cap,0));
		edges.push_back(Edge(to,from,0,0));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}

	ll Maxflow(ll s,ll t) {
		ll flow=0;
		while(1) {
			memset(a,0,sizeof(a));
			queue<ll> Q;
			Q.push(s);
			a[s]=inf;
			while(!Q.empty()) {
				ll x=Q.front();
				Q.pop();
				for(ll i=0; i<G[x].size(); i++) {
					Edge& e=edges[G[x][i]];
					if(!a[e.to]&&e.cap>e.flow) {
						p[e.to]=G[x][i];
						a[e.to]=min(a[x],e.cap-e.flow);
						Q.push(e.to);
					}
				}
				if(a[t]) break;
			}
			if(!a[t]) break;
			for(ll u=t; u!=s; u=edges[p[u]].from) {
				edges[p[u]].flow+=a[t];
				edges[p[u]^1].flow-=a[t];
			}
			flow+=a[t];
		}
		return flow;
	}
};

vector<pair<ll, ll> > mapp[2][maxn];
vector<Edge> me;
ll lowcost[2][maxn];
ll n, m;

void Dijkstra(ll s, ll op) {
	for(ll i = 0; i <= n; i++) {
		lowcost[op][i] = inf;
	}
	lowcost[op][s] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
	pq.push(make_pair(lowcost[op][s], s));
	while(!pq.empty()) {
		pair<ll, int> f = pq.top();
		pq.pop();
		for(int i = 0; i < mapp[op][f.second].size(); i++) {
			pair<ll, int> t(mapp[op][f.second][i].second, mapp[op][f.second][i].first);
			if(lowcost[op][t.second] > t.first + f.first) {
				lowcost[op][t.second] = t.first + f.first;
				pq.push(make_pair(lowcost[op][t.second], t.second));
			}
		}
	}
}

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		scanf("%lld %lld", &n, &m);
		me.clear();
		for(int i = 1; i <= n; i++) {
			mapp[0][i].clear();
			mapp[1][i].clear();
		}
		for(int i = 0;  i < m; i++) {
			ll a, b, c;
			scanf("%lld %lld %lld", &a, &b, &c);
			me.push_back(Edge(a, b, c, 0));
			mapp[0][me[i].from].push_back(make_pair(me[i].to, me[i].cap));
			mapp[1][me[i].to].push_back(make_pair(me[i].from, me[i].cap));
		}
		Dijkstra(1, 0);
		Dijkstra(n, 1);
		ll cost = lowcost[0][n];
		EdmondsKarp ek;
		ek.init(n);
		for(int i = 0; i < m; i++) {
			if(lowcost[0][me[i].from] + me[i].cap + lowcost[1][me[i].to] == cost) {
				ek.AddEdge(me[i].from, me[i].to, me[i].cap);
			}
		}
		cout << ek.Maxflow(1, n) << endl;
	}
}