bzoj 3258 秘密任务

news/2024/6/23 8:16:16

http://www.elijahqi.win/archives/3689
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<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#define ll long long
#define pa pair<ll,int>
#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<pa,vector<pa>,greater<pa> >q;dis1[1]=0;q.push(mp(dis1[1],1));while(!q.empty()){int x=q.top().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<dis1[y]){dis1[y]=dis1[x]+z;q.push(mp(dis1[y],y));}}}}inline void dijkstra2(){memset(dis2,0x3f,sizeof(dis2));memset(flag,0,sizeof(flag));priority_queue<pa,vector<pa>,greater<pa> >q;dis2[n]=0;q.push(mp(dis2[n],n));while(!q.empty()){int x=q.top().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]+z<dis2[y]){dis2[y]=dis2[x]+z;q.push(mp(dis2[y],y));}}}}inline void gao(){init();for (int i=1;i<=m;++i){int x=read(),y=read(),z=read();data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].x=x;data[num].z=z;data[++num].y=x;data[num].next=h[y];h[y]=num;data[num].x=y;data[num].z=z;}dijkstra1();dijkstra2();ll tmp=dis1[n];tot=n;for (int i=1;i<=num;++i){int x=data[i].x,y=data[i].y,z=data[i].z;if (dis1[x]+dis2[y]+z==tmp){if (y==n) {insert1(x,y,a[x]);continue;}++tot;insert1(x,tot,a[x]);insert1(tot,y,a[y]);}}}
}
inline bool bfs(){queue<int>q;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<n;++i) a[i]=read();num=1;cnt=0;s=0;memset(h,0,sizeof(h));build::gao();ll ans=0;while(bfs()) memcpy(cur,h,sizeof(h)),ans+=dfs(1,1LL<<60);memset(dfn,0,sizeof(dfn));num=0;bool flag=1;for (int i=1;i<=build::tot;++i) if (!dfn[i]) tarjan(i);for (int i=1;i<=cnt;++i){if (data[i<<1].z) continue;if (b[fr[i]]==b[to[i]]) continue;if (b[fr[i]]==b[1]&&b[to[i]]==b[n]) continue;flag=0;break;}if (flag) printf("Yes %lld\n",ans);else printf("No %lld\n",ans);}return 0;
}

https://www.xjx100.cn/news/848178.html

相关文章

秘密任务

秘密任务 Description Input 第一行 包含一 个正整数 T&#xff0c;表示有 T组测试数据。接下来 依次是 T组测试数 据。 每组测试数 据的第一行包含两个整N、M。 第二行包含 N - 1个正整数&#xff0c;依次表示 A1&#xff0c;A2&#xff0c; …&#xff0c;AN-1。 接下来…

​如何高效开发一个OA办公系统​?

如何才能高效开发一个OA办公系统&#xff1f;这篇教你使用零代码工具从0-1搭建一个OA办公系统&#xff0c;无需代码基础&#xff0c;只要你懂业务&#xff0c;只需3步即可搭建&#xff01; 先来看看效果—— 系统模板>> https://www.jiandaoyun.com/ 整个系统包含物资管…

RaaS(勒索软件即服务)是什么?这个模型是如何工作的?

Ransomware as a Service是一个英语术语,指的是一种商业模型&#xff0c;其中勒索软件开发者向感兴趣的恶意行为者提供工具&#xff0c;以便他们可以发起勒索软件攻击。使用者通过签约创建恶意软件即服务或加入联盟计划&#xff0c;并分发一系列勒索软件以换取一定比例的利润。…

Vue中如何进行表格合并与拆分

Vue中如何进行表格合并与拆分 在Vue应用程序中&#xff0c;表格是一个非常常见的组件。有时候我们需要对表格进行合并或拆分来满足特定的需求。在本文中&#xff0c;我们将介绍如何在Vue中进行表格的合并和拆分。 如何进行表格合并&#xff1f; 表格合并是指将多行或多列的单…

java企业级开发1

java web开发入门基础 什么是静态&#xff1f;什么是动态&#xff1f;网页的发展史 静态web资源&#xff08;如html页面&#xff09;&#xff1a;指web页面中提供给人们浏览的数据始终是不变的。 动态web资源&#xff08;如jsp&#xff0c;php等&#xff09;&#xff1a;指w…

prezi1破解安装与使用

1.破解安装 ①下载破解安装包 下载地址&#xff1a;http://soft.2128.net/Prezi528_6068.zip ②安装exe文件&#xff08;安装步骤跳过&#xff09;&#xff0c;安装好之后&#xff0c;在prezi安装目录下替换以下两个同名文件 ③打开快捷方式&#xff0c;完成&#xff0c;进入…

【开学季】30款高质量的自学网站,总有一款适合你

小伙伴们注意&#xff1a;公众号的推送机制不再按照时间前后推送了&#xff0c;微信公众号信息流乱序。君哥建议大家把公众号置顶&#xff08;设为星标★&#xff09;&#xff0c;以便第一时间看到推送&#xff0c;方法如下图 万水千山总是情&#xff0c;为君哥三连行不行&…

高校课堂机器人工程方向教学设计不足与工作反思

全人类的科技工作者每一天都将我们的机器人变得越来越智能&#xff0c;越来越像人&#xff1b; 而我们所接受的日常教育却使人越来越机械&#xff0c;越来越像机器…… 引用&#xff1a;https://github.com/mithi/robotics-coursework 机器人系列课程 EDX&#xff1a;机器人M…