秘密任务

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 ] f[i][j]*a[i] f[i][j]∗a[i],将t到y的边权设为 f [ i ] [ j ] ∗ a [ i ] f[i][j]*a[i] 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);}
}

本文链接：https://my.lmcjl.com/post/9251.html