bzoj 3258 秘密任务

bzoj 3258 秘密任务

​​Description Alice听说在一片神奇的大陆MagicLand，有一个古老的传说……很久很久以前，那个时候 MagicStates共和国刚刚 成立。 反对新政府的势力虽已被镇压，但仍然在暗地活动。这一次，情报局得到了一个令人震惊的消息，被软禁 在首都府邸中的Frank ——著名的反对派领袖，秘密逃出首都，去往反对派的大本营。根据相关的情报，Frank计 划通过城市之间 发达的高速公路，经过最短的路程抵达目的地。不妨将 MagicStates共和国简化为由N个城市,M条 高速公路构成的连通的无向图，首都为城市1，反对派的大本营为城市N。每条高速公路连接两个不同的城市，且路 程是已知的。而Frank选择了一条从城市1到城市N的最短路径作为他的逃跑路线。为了阻止Frank，共和国总统决定 在某些城市的高速公路的出入口设立检查 点，在Frank经过检查点时将他逮捕。举例来说，如果有一条高速公路连 接城市u和城市v，在这条公路的城市u或城市v的出入口设立检查点，那么Frank经过高速公路时就会被发现。特别 的是，由于城市N实际上处在反对派的控制下，所以不能在城市N设立检查点。然而在任何城市设立检查点都需要一 定的费用。更具体的，若在城市 u设立k个检查点，就要花费 Au乘以k的代价，其中Au是城市u的相关参数。值得注 意的是，这个代价与这k个检查点具体设在哪些公路的出入口无关,于是，总统责令情报局拟定一个方案，花费最小 的代价使得无论Frank选择哪条最短路线，都会在（除城市N以外）某个城市的高速公路出入口被发现。读到这里， Alice很想知道阻止Frank所需要花费的最小代价，并且她还希 望知道最优方案是否是唯一的。只好再请你帮助她 了。注意，我们称两个方案不同当且仅当存在某城市k，两种方案中在城市 k的检查点的设置（而不仅是数目）是 不同的。 注意，输入文件包含多组测试数据。 Input 第一行包含一个正整数T，表示有T组测试数据。 接下来依次是T组测试数据。 每组测试数据的第一行包含两个整数N、M。 第二行包含N-1个正整数，依次表示A1，A2，…，An-1。 接下来M行，每行三个整数Ui,Vi,Ci,表示一条连接城市Ui和城市Vi的路程等于Ci的高速公路 2≤N≤400,1≤M≤4000，1≤T≤5， 1≤Ai,c≤10^9。无向图可能有重边。

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)的出入口。 HINT

Source 思考了很久发现自己好像会费用流的做法

看了眼范围 再看眼时间榜 觉得显然不可能是费用流

然后苦思冥想 哦最小割即可

所以首先两遍最短路 建网络流的图

怎么建 拆边然后最小割一样因为一条边有两个端点要么选这个要么选那个

所以就直接新建一个点 然后两端权值分别建成g两条边即可

最后在残余网络上跑tarjan 确定找出那些是割边但不一定是割边的边 然后判断是否唯一解

#include#include#include#include#include#include#define ll long long#define pa pair#define mp(x,y) make_pair(x,y)using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if(T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=5000;const int M=11000;struct node{ int x,y,next,z;}data[M<<1];bool stackf[N];int n,m,cur[N],h[N],num,cnt,s,b[N],dfn[N],low[N],q[N],top,a[N],fr[M],to[M],level[N];inline void insert1(int x,int y,int z){ fr[++cnt]=x;to[cnt]=y; data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].z=z; data[++num].y=x;data[num].next=h[y];h[y]=num;data[num].z=0;}namespace build{ struct node{ int x,y,next,z; }data[M];bool flag[550]; ll dis1[500],dis2[500];int h[500],num,tot; inline void init(){ memset(h,0,sizeof(h));num=0; } inline void dijkstra1(){ memset(dis1,0x3f,sizeof(dis1));memset(flag,0,sizeof(flag)); priority_queue,greater >q;dis1[1]=0;q.push(mp(dis1[1],1)); while(!q.empty()){ int x=q-().second;q.pop();if (flag[x]) continue;flag[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (dis1[x]+z,greater >q;dis2[n]=0;q.push(mp(dis2[n],n)); while(!q.empty()){ int x=q-().second;q.pop();if (flag[x]) continue;flag[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (dis2[x]+zq;memset(level,0,sizeof(level));level[1]=1;q.push(1); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1; if (y==n) return 1;q.push(y); } }return 0;}inline ll dfs(int x,ll s){ if (x==n) return s;ll ss=s; for (int &i=cur[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ ll xx=dfs(y,min((ll)z,s));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx; if (!s) return ss; } }return ss-s;}inline void tarjan(int x){ dfn[x]=low[x]=++num;q[++top]=x;stackf[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (!z) continue; if (!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if (stackf[y]) low[x]=min(low[x],dfn[y]); } if (low[x]==dfn[x]){ ++s;int y; do{ y=q[top--];stackf[y]=0;b[y]=s; }while(y!=x); }}int main(){ freopen("bzoj3258.in","r",stdin); int T=read(); while(T--){ n=read();m=read(); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。