In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads. The following are known about the road network:
- People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.
- Different roads may have had different lengths, but all the lengths were positive integers.
Snuke the archeologist found a table with N rows and N columns, A, in the ruin of Takahashi Kingdom. He thought that it represented the shortest distances between the cities along the roads in the kingdom.
Determine whether there exists a road network such that for each u and v, the integer Au,v at the u-th row and v-th column of A is equal to the length of the shortest path from City u to City v. If such a network exist, find the shortest possible total length of the roads.
- 1≤N≤300
- If i≠j, 1≤Ai,j=Aj,i≤109.
- Ai,i=0
相当于最小割 剪去每个不必要的边(在矩阵里是点) 每个点求到其他点的最短路 如果长度大于最短路则删去 如果等于就取节点最多的
#include<math.h>#include<string.h>#include<iostream>#include<stdio.h>#include<algorithm>#include<sstream> //istringstream stm(string); stm >> x;#include<vector>#include<queue>#define INF 2139062143#define inf -2139062144#define ll long longusing namespace std;const int maxn = 1005;ll a[305][305];ll tempa[305][305];struct Edge { ???ll from, to, dist; ???Edge(ll u, ll v, ll d) : from(u), to(v), dist(d) {}};struct HeapNode { ???ll d, u; ???bool operator<(const HeapNode &rhs) const { ???????return d > rhs.d; ???}};struct Dijkstra { ???ll n, m; ???vector <Edge> edges; ???vector<ll> G[maxn]; ???bool done[maxn]; ???ll d[maxn]; ???ll roadcount[maxn]; ???ll p[maxn]; ????//×??ì?·?Dμ?é?ò?ì??? ???vector<ll> path; ???void init(ll n) { ???????this->n = n; ???????for (ll i = 0; i < n; i++) G[i].clear(); ???????edges.clear(); ???????path.clear(); ???} ???void addEdge(ll from, ll to, ll dist) { ???????edges.push_back(Edge(from, to, dist)); ???????m = edges.size(); ???????G[from].push_back(m - 1); ???} ???void dijkstra(ll s) { ???//′ósμ??aê? ???????priority_queue <HeapNode> Q; ???????for (ll i = 0; i <= n; i++) d[i] = INF; ???????for (ll i = 0; i <= n; i++) roadcount[i] = 0; ???????d[s] = 0; ???????memset(done, 0, sizeof(done)); ???????Q.push((HeapNode) { ???????????0, s ???????}); ???????while (!Q.empty()) { ???????????HeapNode x = Q.top(); ???????????Q.pop(); ???????????ll u = x.u; ???????????if (done[u]) continue; ???????????done[u] = true; ???????????for (ll i = 0; i < G[u].size(); i++) { ???????????????Edge &e = edges[G[u][i]]; ???????????????if (d[e.to] > d[u] + e.dist) { ???????????????????d[e.to] = d[u] + e.dist; ???????????????????roadcount[e.to] = roadcount[u] + 1; ???????????????????p[e.to] = G[u][i]; ???????????????????Q.push((HeapNode) { ???????????????????????d[e.to], e.to ???????????????????}); ???????????????} else { ???????????????????if(d[e.to] == d[u] + e.dist) { ???????????????????????roadcount[e.to] = max(roadcount[e.to],roadcount[u] + 1); ???????????????????} ???????????????} ???????????} ???????} ???} ???void findpath(ll x, ll end) { ???????path.clear(); ???????path.push_back(x); ???????findd(x, end); ???} ???void findd(ll x, ll end) { ???????if (x == end) ???????????return; ???????else { ???????????path.push_back(this->edges[this->p[x]].from); ???????????findd(this->edges[this->p[x]].from, end); ???????} ???}};int main() { ???ll n; ???scanf("%lld",&n); ???Dijkstra dj; ???dj.init(n); ???for(ll i=0; i<n; i++) { ???????for(ll j=0; j<n; j++) { ???????????scanf("%lld",&a[i][j]); ???????????tempa[i][j] = a[i][j]; ???????????if(i != j) ???????????????dj.addEdge(i,j,a[i][j]); ???????} ???} ???bool flag = true; ???for(ll i=0; i<n && flag; i++) { ???????dj.dijkstra(i); ???????for(ll j=0; j<n; j++) { ???????????if(a[i][j] > dj.d[j]) ???flag = false; ???????????if(dj.roadcount[j] > 1) { ???????????????tempa[i][j] = 0; ???????????????tempa[j][i] = 0; ???????????} ???????} ???} ???if(!flag) ???printf("-1\n"); ???else { ???????ll anss = 0; ???????for(ll i=0; i<n; i++) { ???????????for(ll j=0; j<n; j++) { ???????????????anss += tempa[i][j]; ???????????} ???????} ???????printf("%lld\n",anss / 2); ???} ???return 0;}AtCoder Regular Contest 083 ?D:Restoring Road Network
原文地址：http://www.cnblogs.com/Aragaki/p/7533161.html