eclipse网站开发教程,网络设计中网络设备选择的原则,wordpress会员内容,网站论坛建设正题
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id3258 题目大意
一张无向图#xff0c;路有边权#xff0c;在想要封锁某条路可以在该路两边的任意一点设置检查站(一个站只能封锁一条路)#xff0c;在iii点建立一个检查站要AiA_iAi元。
求最少的费用封…正题
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id3258 题目大意
一张无向图路有边权在想要封锁某条路可以在该路两边的任意一点设置检查站(一个站只能封锁一条路)在iii点建立一个检查站要AiA_iAi元。
求最少的费用封锁所有的最短路径并询问封锁方案是否唯一 解题思路
先从111开始一遍最短路fff然后从nnn开始再跑一次最短路f2f2f2
若一个点fxf2xfnf_xf2_xf_nfxf2xfn那么该点是1∼n1\sim n1∼n的某条最短路上的一个点。 若一条边fxwfyf_xwf_yfxwfy那么该边是某条最短路上的边。
然后我们将这些点和边拿出来跑最小割即可求出第一问。
我们考虑如何求第二问为了优化我们发现每一条边可以有两个权值(在两个检查点中任何一个)所以我们将一条边拆成两条边和一个中间点。
现在我们考虑求出最小割的必割边若这些必割边的容量之和就是最小割那么这就是唯一的方案。
如何求出必割边 ∗*∗结论:::对于一条边x,yx,yx,y在残量网络上sss可以到达xxx且yyy可以到达ttt那么该边是必割边。 证明:在残量网络上sss可以到达xxx且yyy可以到达ttt那么说明若该边不割那么sss就可以通过该边到达ttt。假设在sss到xxx的路上有同样长度的一条道路且割掉后可以使sss到达xxx那么在残量网络上该边的流量必定为0因为切割掉x−gt;yx-gt;yx−y的流量也必定会经过该边所以在残量网络上sss就不可以到达xxx了。所以该假设不成立。 证毕
所以我们在残量网络上跑两次dfsdfsdfs然后一条一条边的判断即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N5010,inf1e18;
struct Edge_Node{ll to,next,w;
}a[N*2],e[N*2];
ll T,ls[N],tot1,n,m,c[N],f[N],dep[N],s,t,ans,cnt,flow,f2[N],get[N];
bool v[N];
queueint q;
void adde(ll x,ll y,ll w)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;
}
void addl(ll x,ll y,ll w)
{e[cnt].toy;e[cnt].nextls[x];ls[x]cnt;e[cnt].ww;
}
void spfa(ll s)
{memset(f,127,sizeof(f));for(int i1;in;i)f[i]inf;q.push(s);f[s]0;v[s]1;while(!q.empty()){ll xq.front();q.pop();v[x]0;for(ll ils[x];i;ie[i].next){ll ye[i].to;if(f[x]e[i].wf[y]){f[y]f[x]e[i].w;if(!v[y])v[y]1,q.push(y);}}}
}
void spfa2(ll s)
{memset(f2,127,sizeof(f2));for(int i1;in;i)f2[i]inf;q.push(s);f2[s]0;v[s]1;while(!q.empty()){ll xq.front();q.pop();v[x]0;for(ll ils[x];i;ie[i].next){ll ye[i].to;if(f2[x]e[i].wf2[y]){f2[y]f2[x]e[i].w;if(!v[y])v[y]1,q.push(y);}}}
}
bool bfs()
{memset(dep,0,sizeof(dep));while(!q.empty()) q.pop();q.push(s);dep[s]1;while(!q.empty()){ll xq.front();q.pop();for(ll ils[x];i;ia[i].next){ll ya[i].to;if(!dep[y]a[i].w){dep[y]dep[x]1;if(yt) return true;q.push(y);}}}return false;
}
ll dinic(ll x,ll flow)
{ll rest0,k;if(xt) return flow;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(dep[x]1dep[y]a[i].w){rest(kdinic(y,min(a[i].w,flow-rest)));a[i].w-k;a[i^1].wk;if(restflow) return flow;}}if(!rest) dep[x]0;return rest;
}
void netflow()
{while(bfs())ansdinic(s,inf);
}
void dfs(ll x,ll op)
{if(get[x]) return;get[x]op;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(!a[i^(op-1)].w) continue;dfs(y,op);}
}
int main()
{scanf(%lld,T);while(T--){memset(ls,0,sizeof(ls));totcnt1;scanf(%lld%lld,n,m);s1;tn;ansflow0;c[n]inf;for(ll i1;in;i)scanf(%lld,c[i]);for(ll i1;im;i){ll x,y,w;scanf(%lld%lld%lld,x,y,w);addl(x,y,w);addl(y,x,w);}spfa(1);spfa2(n);memset(ls,0,sizeof(ls));for(int i1;in;i)get[i](f[i]f2[i]f[n]);for(ll i2;icnt;i){ll xe[i^1].to,ye[i].to;if(!get[x]||!get[y]) continue;if(f[x]e[i].wf[y]){n;adde(x,n,c[x]); adde(n,y,c[y]);}}netflow();memset(get,0,sizeof(get));dfs(1,1);dfs(t,2);for(ll i1;in;i)for(ll jls[i];j;ja[j].next)if(get[i]get[a[j].to]get[i]!get[a[j].to])flowa[j].w;if(flowans) printf(Yes);else printf(No);printf( %lld\n,ans);}
}
