Description
- 给定无向图，有边权和点权，删去一条边的代价为这条边的任意一个顶点的权值，求一个最小代价的删边方案，使得1到n的在原图中的最短路都被断开。问最小代价，以及这个方案是否唯一。
- 2 ≤ N ≤ 400, 1 ≤ M ≤ 4 00 0，1 ≤ T ≤ 5，1 ≤ Ai, c ≤ 10^9。无向图可能有重边 。
Solution（一些很显然的东西）
- 显然建出最短路图，然后需要将最短路图割开，裸的最小割模型，有向边就是最短路图的边，流量为两个顶点点权最小值。跑网络流即可得出最小代价。
- 怎么知道最小割是否唯一呢？
- 首先简化模型：一条边的流量如果为顶点点权的min的话，还要讨论顶点的点权是否一样，再看一看这条边割了没有，这么多讨论十分难做，不如将这条边拆成两条边，一条边的流量为一个点的点权。
- 然后我们运用必割边，如果必割边的流量之和小于最大流，那么剩下的部分一定由可能割的边组成，自然就没有唯一的方案了。
- 问题来了，什么是必割边？
必割边（重点在这里）
- 必割边就是任意一个最小割都存在的边。
- 如果一条边的两个端点u,v分别能在残量网络中与S和T相连，那么这条边就是必割边。
- 如果这条边(u,v)没有割的话，必然可以再从S到u到v到T再流一条过去，流量就会变大，就不满足最大流的性质 ，所以这条边一定是割掉了的。
- 从S和T分别遍历一波残量网络流好了。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 405
#define maxm 8005
#define maxd 1005
#define maxt 9005
#define inf 1e18
#define I(i) ((i&1)?i+1:i-1)
#define ll long long
using namespace std;int T,n,m,i,j,k,x,y,num;
int em,e[maxm*2],nx[maxm*2],ls[maxt],tot[maxn],to[maxn][maxm/2];
ll a[maxn],ec[maxm*2],to_c[maxn][maxm/2],z,dis[maxt],ans,sum;
int t,w,d[maxd],vis[maxt],bz[maxt];void SPFA(){memset(vis,0,sizeof(vis));memset(dis,127,sizeof(dis));t=0,w=1,d[1]=1,vis[1]=1,dis[1]=0;while (t<w){t=(t+1)%maxd; int x=d[t]; vis[x]=0;for(int i=1;i<=tot[x];i++) {int y=to[x][i];if (dis[x]+to_c[x][i]<dis[y]){dis[y]=dis[x]+to_c[x][i];if (!vis[y]) vis[y]=1,w=(w+1)%maxd,d[w]=y;}}}
}void insert(int x,int y,ll z){em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em]=z;em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; ec[em]=0;
}int BFS(int S,int T){memset(dis,127,sizeof(dis));t=0,w=1,d[1]=S,dis[S]=0;while (t<w){int x=d[++t];for(int i=ls[x];i;i=nx[i]) if (dis[x]+1<dis[e[i]]&&ec[i]){dis[e[i]]=dis[x]+1;d[++w]=e[i];}}return dis[T]<1e18;
}ll dfs(int x,ll p){if (x==n) return p;ll res=p;for(int i=ls[x];i&&res;i=nx[i]) if (dis[x]+1==dis[e[i]]&&ec[i]){ll tmp=dfs(e[i],min(res,ec[i]));res-=tmp;ec[i]-=tmp,ec[I(i)]+=tmp;}return p-res;
}ll dinic(){ll ans=0;while (BFS(1,n)){for(ll tmp=dfs(1,inf);tmp;tmp=dfs(1,inf))ans+=tmp;}return ans;
}void BFS2(int S){t=0,w=1,d[1]=S,bz[S]=1;while (t<w){int x=d[++t];for(int i=ls[x];i;i=nx[i]) if (!bz[e[i]]&&ec[i]){bz[e[i]]=1;d[++w]=e[i];}}
}void BFS3(int S){t=0,w=1,d[1]=S,bz[S]=2;while (t<w){int x=d[++t];for(int i=ls[x];i;i=nx[i]) if (!bz[e[i]]&&ec[I(i)]){bz[e[i]]=2;d[++w]=e[i];}}
}int main(){scanf("%d",&T);while (T--){scanf("%d%d",&n,&m);for(i=1;i<n;i++) scanf("%lld",&a[i]);a[n]=inf;memset(tot,0,sizeof(tot));for(i=1;i<=m;i++) {scanf("%d%d%lld",&x,&y,&z);tot[x]++,to[x][tot[x]]=y,to_c[x][tot[x]]=z;tot[y]++,to[y][tot[y]]=x,to_c[y][tot[y]]=z;}SPFA();em=0,memset(ls,0,sizeof(ls)),num=n;for(i=1;i<=n;i++) for(j=1;j<=tot[i];j++){k=to[i][j];if (dis[i]+to_c[i][j]==dis[k]){++num;insert(i,num,a[i]);insert(num,k,a[k]);}}ans=dinic();memset(bz,0,sizeof(bz));BFS2(1);BFS3(n);sum=0;for(x=1;x<=num;x++) for(i=ls[x];i;i=nx[i]) if (i&1&&bz[x]+bz[e[i]]==3)sum+=ec[i]+ec[I(i)];if (sum<ans) printf("No %lld\n",ans);else printf("Yes %lld\n",ans);}
}
本文链接：https://my.lmcjl.com/post/9220.html
展开阅读全文
4 评论