秘密任务

Description

在这里插入图片描述

Input

第一行包含一个正整数 T，表示有 T组测试数据。接下来依次是 T组测试数据。

每组测试数据的第一行包含两个整N、M。

第二行包含 N - 1个正整数，依次表示 A1，A2， …，AN-1。

接下来 M行，每行为三个整数： ui、vi、ci，表示一条连接城市ui和城市 vi的路程等于 ci的高速公路。

Output

输出 T行，依次表示每组测试数据的答案。若最优方案唯一则输出 ”Yes”和最小代价，否则输出 ”No ”和最小代价。字符串和整数之间请用一个空格隔开。

Sample Input

3
3 3
2 4
1 3 23
3 2 12
2 1 11
4 4
3 2 2
1 2 1
2 3 1
3 4 1
4 1 1
3 4
3 2
1 2 1
2 3 2
2 3 19
3 1 4

Sample Output

Yes 4
Yes 3
No 2

【样例解释】
第 1组测试数据：最优方案是在城市 1设立两个检查点。
第 2组测试数据：最优方案是城市 1的高速公路 (1, 4 )的出入口设立检查点。
第 3组测试数据：最优方案是在城市 2设立一个检查点，不过既可以设置在高速公路 (1, 2)的出入口，也可以设置在高速公路 (2, 3)的出入口。

Data Constraint

对于 10% 的数据： 2 ≤ N ≤ 10 , 1 ≤ M ≤ 20。

另有 40% 的数据：最优方案是唯一的。

对于 10 0% 的数据： 2 ≤ N ≤ 400, 1 ≤ M ≤ 4 00 0，1 ≤ T ≤ 5，1 ≤ Ai, c ≤ 10^9。无向图可能有重边。

题目大意

给你一个图，要求求出其最短路图中的最小割，并且判断方案是否唯一。

题解

这道题真的好麻烦…

首先我们要求出最短路图（就是跑一遍最短路求出dis，然后再看每条边是否是最短路上的即可）。

然后我们设f[i][j]表示i到j有几条边在最短路上，那么我们就可以重新建出一张图。

建图方法如下：

1.将一条边之间增加一个点：

x————————>y ==> x ————>t————>y

这个点t是新建的一个节点。

2.将x到t的边权设为 $f [i] [j] * a [i]$ ,将t到y的边权设为 $f [i] [j] * a [i]$ ，然后.就可以啦

3.注意特判如果y是n，那么要将t到y的边权设为INF（不能被割掉）。

然后我们就可以愉快的在上面跑最小割（最大流）啦！

跑出来的就是第二问的答案。

那么我们怎么求第一问的答案呢？

显然，如果我们每条必割边的边权之和等于最小割，那么我们最小割集里面每条边都是必割边，那么答案显然唯一（就是Yes）。

反之则为No。

我们可以在残量网络中整理出与S（源点）相连的集合和与T（汇点）相连的集合，那么如果一条边的两个端点分别属于S集合和T集合，那么我们就可以认为这是必割边。

证明显然。

这题细节好多…

code

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 1005
#define M 60005
#define ll long long
#define mem(x,y) memset(x,y,sizeof x)
using namespace std;
//For 2000 yuan
int T,n,m,a[N],tot,jl[N][N],r[N][N],bz[M],f[N][N],w[M*2],h,t,tov[M*2],last[M],next[M*2],len[M*2],tot1,X[M],Y[M];
ll nn,ans,pre[M],c[M],flow[M],dis[M];
int ins1(int x,int y,int z){jl[x][++jl[x][0]]=y,r[x][jl[x][0]]=z,jl[y][++jl[y][0]]=x,r[y][jl[y][0]]=z;}
int ins(int x,int y,int z){tov[++tot1]=y,next[tot1]=last[x],len[tot1]=z,last[x]=tot1,tov[++tot1]=x,next[tot1]=last[y],len[tot1]=0,last[y]=tot1;}
ll bfs(int x,int y)
{mem(pre,0),mem(c,0),mem(w,0),mem(flow,0),w[1]=x,pre[x]=x,flow[y]=0,flow[x]=1e9;int h=0,t=1;while (h<t){int z=w[++h];if (z==y)break;for (int i=last[z];i;i=next[i])if (!pre[tov[i]]&&len[i])w[++t]=tov[i],pre[tov[i]]=z,flow[tov[i]]=min(flow[z],(ll)len[i]),c[tov[i]]=i;}return flow[y];
} 
ll getans(int x,int y)
{ll ans=0,t=bfs(x,y);while (t){for (int i=y;i!=x;i=pre[i])len[c[i]]-=t,len[c[i]^1]+=t;ans+=t,t=bfs(x,y);}return ans;
}
int main()
{scanf("%d",&T);while (T--){scanf("%d%d",&n,&m),tot1=1,nn=n,mem(last,0),mem(bz,0),mem(w,0),mem(jl,0),mem(f,0),mem(X,0),mem(Y,0);for (int i=1;i<n;i++)scanf("%d",&a[i]);for (int i=1,z,y,x;i<=m;i++)scanf("%d%d%d",&x,&y,&z),ins1(x,y,z);mem(dis,63),h=0,w[t=1]=1,bz[1]=1,dis[1]=0;while (h<t){int x=w[++h];for (int i=1;i<=jl[x][0];i++)if (dis[x]+r[x][i]<dis[jl[x][i]]){dis[jl[x][i]]=r[x][i]+dis[x];if (!bz[jl[x][i]])w[++t]=jl[x][i],bz[jl[x][i]]=1;}bz[x]=0;}for (int i=1;i<=n;i++)for (int j=1;j<=jl[i][0];j++)if (dis[i]+r[i][j]==dis[jl[i][j]])f[i][jl[i][j]]++;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (f[i][j])nn++,ins(i,nn,(i==n)?1e9:f[i][j]*a[i]),ins(nn,j,(j==n)?1e9:f[i][j]*a[j]);ans=getans(1,n);mem(w,0),h=0,t=1,w[1]=1,X[++X[0]]=1,mem(bz,0),bz[1]=1;while (h<t){int x=w[++h];for (int i=last[x];i;i=next[i])if (len[i]&&!bz[tov[i]])w[++t]=tov[i],X[++X[0]]=tov[i],bz[tov[i]]=1;}mem(w,0),h=0,t=1,w[1]=n,mem(bz,0),bz[n]=1,Y[++Y[0]]=n;while (h<t){int x=w[++h];for (int i=last[x];i;i=next[i])if (len[i^1]&&!bz[tov[i]])w[++t]=tov[i],Y[++Y[0]]=tov[i],bz[tov[i]]=1;}mem(bz,0);for (int i=1;i<=Y[0];i++)bz[Y[i]]=1;ll sum=0;for (int ii=1,x;ii<=X[0];ii++){x=X[ii];for (int i=last[x];i;i=next[i])if (len[i]==0&&bz[tov[i]])sum+=len[i^1];}(sum==ans)?printf("Yes "):printf("No ");printf("%d\n",ans);}
}