題干：

As the current heir of a wizarding family with a long history,unfortunately, you find yourself forced to participate in the cruel Holy Grail War which has a reincarnation of sixty years.However,fortunately,you summoned a Caster Servant with a powerful Noble Phantasm.When your servant launch her Noble Phantasm,it will construct a magic field,which is actually a?directed?graph?consisting of?n vertices?and?m edges.More specifically,the graph satisfies the following restrictions :

• Does not have multiple edges(for each pair of vertices?x?and?y, there is at most one edge between this pair of vertices in the graph) and does not have self-loops(edges connecting the vertex with itself).
• May have?negative-weighted edges.
• Does not have a?negative-weighted loop.
• n<=300?,?m<=500.

Currently,as your servant's Master,as long as you add extra?6?edges to the graph,you will beat the other 6 masters to win the Holy Grail.

However，you are subject to the following restrictions when you add the edges to the graph:

• Each time you add an edge whose cost is c,it will cost you c units of Magic Value.Therefore,you need to add an edge which has the lowest weight(it's probably that you need to add an edge which has a negative weight).
• Each time you add an edge to the graph,the graph must not have negative loops,otherwise you will be engulfed by the Holy Grail you summon.

Input

Input data contains multiple test cases. The first line of input contains integer?t?— the number of testcases (1 \le t \le 51≤t≤5).

For each test case,the first line contains two integers n,m,the number of vertices in the graph, the initial number of edges in the graph.

Then m lines follow, each line contains three integers?x, y and w?(0 \le x,y<n0≤x,y<n,-10^9?109≤w≤10^9109,?x \not = yx?=y) denoting an edge from vertices x to y (0-indexed) of weight w.

Then 6 lines follow, each line contains two integers?s,t?denoting?the starting vertex?and?the ending vertex?of the edge you need to add to the graph.

It is guaranteed that there is not an edge starting from?s to t?before you add any edges and there must exists such an edge which has the lowest weight and satisfies the above restrictions, meaning the solution absolutely exists for each query.

Output

For each test case,output?66?lines.

Each line contains the weight of the edge you add to the graph.

樣例輸入復制

1 10 15 4 7 10 7 6 3 5 3 3 1 4 11 0 6 20 9 8 25 3 0 9 1 2 15 9 0 27 5 2 0 7 3 -5 1 7 21 5 0 1 9 3 16 1 8 4 4 1 0 3 6 9 2 1 8 7 0 4

樣例輸出復制

-11 -9 -45 -15 17 7

題目大意：

給一張n個點m條邊的帶權有向圖（權值可能為負），問你依次進行6個操作，每個操作給定起點和終點，讓你在起點終點之間加一條邊，問你這條邊的邊權最小是多少，可以保證新圖中無負環。

解題報告：

二分權值判負環check就行了。然而標解好像不用二分，直接找到s到t的最短路就可以了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 500 + 5; const ll PYL = 1e12; int n,m; int tot,head[MAX]; struct Edge {int u,v;int ne;ll w; } e[MAX*100]; void add(int u,int v,ll w) {e[++tot].u = u;e[tot].v = v;e[tot].w = w;e[tot].ne = head[u];head[u] = tot; } ll dis[MAX]; int cnt[MAX]; bool vis[MAX]; bool spfa(int st) {for(int i = 1; i<=n+1; i++) dis[i] = 1e12,vis[i] = 0,cnt[i] = 0;;queue<int> q;dis[st]=0;q.push(st);vis[st]=1; cnt[st]=1;while(q.size()) {int cur = q.front();q.pop();vis[cur]=0;for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].v;if(dis[v] <= dis[cur] + e[i].w) continue;dis[v] = dis[cur] + e[i].w;if(!vis[v]) {cnt[v]++; vis[v]=1; q.push(v);if(cnt[v] > n) return 0;//}}}return 1;//沒有負環返回1 } int U[MAX],V[MAX],W[MAX]; int main() {int T;cin>>T;while(T--) {scanf("%d%d",&n,&m);for(int i = 1; i<=m; i++) scanf("%d%d%d",&U[i],&V[i],&W[i]),U[i]++,V[i]++;for(int Q = 1; Q<=6; Q++) {ll l = 0,r = 2e12,ans,mid;int st,ed;scanf("%d%d",&st,&ed);st++,ed++;while(l<=r) {mid = (l+r)>>1;tot=0;memset(head,-1,sizeof head);for(int i = 1; i<=m; i++) add(U[i],V[i],W[i]);for(int i = 1; i<=n; i++) add(n+1,i,0);add(st,ed,mid-PYL);if(spfa(n+1)) ans = mid,r = mid-1;else l = mid+1;}U[++m] = st,V[m] = ed,W[m] = ans-PYL;printf("%lld\n",ans-PYL);}}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【2019icpc南京站网络赛 - H】Holy Grail（最短路，spfa判负环）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。