[2018.3.30集训]path-对偶图-最小割

题目大意

给出一个包含 n + 1 个结点的有向图，结点的编号为 0 到 n。图中有 m 条
有向边，第 i 条有向边起点为 ui，终点为 vi，且长度为 wi。并且这些边还满
足如下的性质：
• 对任意一条边，满足 ui < vi。
• 不存在两条边 i; j 使得 ui < uj < vi < vj。
除了结点 0 和结点 n 以外，其余的每个结点都有颜色。现在需要你找出一条从结点 0 走到结点 n 的最短路径。对于任意一种颜色，这条路径要么经过了这种颜色的所有结点，要么就不经过这种颜色的任意一个结点。如果不存在这样的路径，请输出 -1，否则输出最短路径的长度。

题解

考场上对偶图都想到了却不会建限制边QAQ

首先，平面图最小割可以转对偶图最短路。
所以反过来也可以。

于是首先转成对偶图最小割建图，每条边在对偶后成为连接它在原图两侧的两个平面对偶后的点的边。

接下来就是考虑限制了。
考虑对每种颜色建一个节点，对于一条边，从它对偶后指向的节点，向它所覆盖的所有边的起点的颜色的节点连双向$Inf$边。
这么连的含义是，选择了这条边就不能选择这种颜色。
于是，由于不选择这种颜色，就需要对于每一种以该颜色为起点的边，割掉完全覆盖掉它的某一条边。
于是，双向$Inf$边保证了上述条件，使得所有覆盖了该颜色的边的边由于该颜色的节点而互相联通，必须要一起割。

最后，对于那些只能到达$0$和$n$中的一个的节点，将它们的颜色的点向汇点连双向$Inf$边，代表这种颜色不能选。
于是就完成了!

代码:

#include<bits/stdc++.h> using namespace std;inline int read() {int x=0;char ch=getchar();while(ch<'0' || '9'<ch)ch=getchar();while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();return x; }const int N=1009;struct ed {int u,v,w;bool cover;bool operator < (ed o)const{return v-u<o.v-o.u;} };int n,m,s,t,c[N],fl[N],Inf,tot; int g[N][N],id[N],rid[N]; bool cover[N],connect[N]; ed e[N*N];namespace flow {const int P=2009;const int M=100009;int to[M<<1],nxt[M<<1],w[M<<1],beg[P],tote=1;int q[P],dis[P];inline void add(int u,int v,int uc,int vc){to[++tote]=v;nxt[tote]=beg[u];w[tote]=uc;beg[u]=tote;to[++tote]=u;nxt[tote]=beg[v];w[tote]=vc;beg[v]=tote;}inline bool bfs(){memset(dis,0,sizeof(dis));q[1]=s;dis[s]=1;for(int l=1,r=1,u=q[1];l<=r;u=q[++l])for(int i=beg[u];i;i=nxt[i])if(w[i]>0 && !dis[to[i]])dis[to[i]]=dis[u]+1,q[++r]=to[i];return dis[t];}inline int dfs(int u,int flow){if(u==t || !flow)return flow;int cost=0;for(int i=beg[u],f;i;i=nxt[i])if(w[i]>0 && dis[to[i]]==dis[u]+1){f=dfs(to[i],min(flow-cost,w[i]));w[i]-=f;w[i^1]+=f;cost+=f;if(cost==flow)break;}if(!cost)dis[u]=-1;return cost;}inline int dinic(){int ret=0;while(bfs() && ret<Inf)ret+=dfs(s,Inf);return ret<Inf?ret:-1;} }using namespace flow;int main() {freopen("path.in","r",stdin);freopen("path.out","w",stdout);memset(g,127,sizeof(g));Inf=g[0][0]+1;n=read();m=read();for(int i=1;i<n;i++)c[i]=read();for(int i=1,u,v;i<=m;i++){u=read();v=read();g[u][v]=g[v][u]=min(g[u][v],read());}fl[n]=1;for(int i=n;i>=0;i--)for(int j=i+1;j<=n;j++)fl[i]|=(fl[j] && g[i][j]<Inf);m=0;for(int i=0;i<=n;i++)if(fl[i]){rid[id[i]=++m]=i;for(int j=0;j<i;j++)if(g[j][i]<Inf && id[j] && id[j]!=m-1)e[++tot]=(ed){id[j],m,g[j][i],0};}if(id[n]!=m)return puts("-1"),0;e[++tot]=(ed){1,m,0,0};sort(e+1,e+tot+1);for(int i=1;i<=tot;i++)printf("%d:%d %d %d\n",i,e[i].u,e[i].v,e[i].w);s=tot,t=tot+n+1;for(int i=1;i<=n-1;i++)if(fl[i])add(tot+c[i],t,Inf,Inf);for(int i=1;i<=tot;i++){for(int j=1;j<i;j++)if(!e[j].cover && e[i].u<=e[j].u && e[j].v<=e[i].v)e[j].cover=1,add(i,j,e[j].w,Inf);for(int j=e[i].u+1;j<=e[i].v-1;j++)if(!cover[j])cover[j]=1,add(i,tot+c[rid[j]],Inf,Inf);for(int j=e[i].u;j<e[i].v;j++)if(!connect[j])connect[j]=1,add(i,t,g[rid[j]][rid[j+1]],0);}printf("s %d\n",dinic());return 0; }

转载于:https://www.cnblogs.com/zltttt/p/8711609.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的[2018.3.30集训]path-对偶图-最小割的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。