秘密任务

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

秘密任务

Description

在这里插入图片描述

Input

第一行 包含一 个正整数 T,表示有 T组测试数据。接下来 依次是 T组测试数 据。

每组测试数 据的第一行包含两个整N、M。

第二行包含 N - 1个正整数,依次表示 A1,A2, …,AN-1。

接下来 M行,每 行为三个 整数: ui、vi、ci,表示一条连接城市ui和城市 vi的路程等于 ci的高速公路。

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

Data Constraint

对于 10% 的数据: 2 ≤ N ≤ 10 , 1 ≤ M ≤ 20。

另有 40% 的数据: 最优 方案 是唯一 的。

对于 10 0% 的数据: 2 ≤ N ≤ 400, 1 ≤ M ≤ 4 00 0,1 ≤ T ≤ 5,1 ≤ Ai, c ≤ 10^9。无向图可能 有重边 。

题目大意

给你一个图,要求求出其最短路图中的最小割,并且判断方案是否唯一。

题解

这道题真的好麻烦…

首先我们要求出最短路图(就是跑一遍最短路求出dis,然后再看每条边是否是最短路上的即可)。

然后我们设f[i][j]表示i到j有几条边在最短路上,那么我们就可以重新建出一张图。

建图方法如下:

1.将一条边之间增加一个点:

x————————>y ==> x ————>t————>y

这个点t是新建的一个节点。

2.将x到t的边权设为 f [ i ] [ j ] ∗ a [ i ] f[i][j]*a[i] f[i][j]a[i],将t到y的边权设为 f [ i ] [ j ] ∗ a [ i ] f[i][j]*a[i] f[i][j]a[i],然后.就可以啦

3.注意特判如果y是n,那么要将t到y的边权设为INF(不能被割掉)。

然后我们就可以愉快的在上面跑最小割(最大流)啦!

跑出来的就是第二问的答案。

那么我们怎么求第一问的答案呢?

显然,如果我们每条必割边的边权之和等于最小割,那么我们最小割集里面每条边都是必割边,那么答案显然唯一(就是Yes)。

反之则为No。

我们可以在残量网络中整理出与S(源点)相连的集合和与T(汇点)相连的集合,那么如果一条边的两个端点分别属于S集合和T集合,那么我们就可以认为这是必割边。

证明显然。

这题细节好多…

code

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 1005
#define M 60005
#define ll long long
#define mem(x,y) memset(x,y,sizeof x)
using namespace std;
//For 2000 yuan
int T,n,m,a[N],tot,jl[N][N],r[N][N],bz[M],f[N][N],w[M*2],h,t,tov[M*2],last[M],next[M*2],len[M*2],tot1,X[M],Y[M];
ll nn,ans,pre[M],c[M],flow[M],dis[M];
int ins1(int x,int y,int z){jl[x][++jl[x][0]]=y,r[x][jl[x][0]]=z,jl[y][++jl[y][0]]=x,r[y][jl[y][0]]=z;}
int ins(int x,int y,int z){tov[++tot1]=y,next[tot1]=last[x],len[tot1]=z,last[x]=tot1,tov[++tot1]=x,next[tot1]=last[y],len[tot1]=0,last[y]=tot1;}
ll bfs(int x,int y)
{mem(pre,0),mem(c,0),mem(w,0),mem(flow,0),w[1]=x,pre[x]=x,flow[y]=0,flow[x]=1e9;int h=0,t=1;while (h<t){int z=w[++h];if (z==y)break;for (int i=last[z];i;i=next[i])if (!pre[tov[i]]&&len[i])w[++t]=tov[i],pre[tov[i]]=z,flow[tov[i]]=min(flow[z],(ll)len[i]),c[tov[i]]=i;}return flow[y];
} 
ll getans(int x,int y)
{ll ans=0,t=bfs(x,y);while (t){for (int i=y;i!=x;i=pre[i])len[c[i]]-=t,len[c[i]^1]+=t;ans+=t,t=bfs(x,y);}return ans;
}
int main()
{scanf("%d",&T);while (T--){scanf("%d%d",&n,&m),tot1=1,nn=n,mem(last,0),mem(bz,0),mem(w,0),mem(jl,0),mem(f,0),mem(X,0),mem(Y,0);for (int i=1;i<n;i++)scanf("%d",&a[i]);for (int i=1,z,y,x;i<=m;i++)scanf("%d%d%d",&x,&y,&z),ins1(x,y,z);mem(dis,63),h=0,w[t=1]=1,bz[1]=1,dis[1]=0;while (h<t){int x=w[++h];for (int i=1;i<=jl[x][0];i++)if (dis[x]+r[x][i]<dis[jl[x][i]]){dis[jl[x][i]]=r[x][i]+dis[x];if (!bz[jl[x][i]])w[++t]=jl[x][i],bz[jl[x][i]]=1;}bz[x]=0;}for (int i=1;i<=n;i++)for (int j=1;j<=jl[i][0];j++)if (dis[i]+r[i][j]==dis[jl[i][j]])f[i][jl[i][j]]++;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (f[i][j])nn++,ins(i,nn,(i==n)?1e9:f[i][j]*a[i]),ins(nn,j,(j==n)?1e9:f[i][j]*a[j]);ans=getans(1,n);mem(w,0),h=0,t=1,w[1]=1,X[++X[0]]=1,mem(bz,0),bz[1]=1;while (h<t){int x=w[++h];for (int i=last[x];i;i=next[i])if (len[i]&&!bz[tov[i]])w[++t]=tov[i],X[++X[0]]=tov[i],bz[tov[i]]=1;}mem(w,0),h=0,t=1,w[1]=n,mem(bz,0),bz[n]=1,Y[++Y[0]]=n;while (h<t){int x=w[++h];for (int i=last[x];i;i=next[i])if (len[i^1]&&!bz[tov[i]])w[++t]=tov[i],Y[++Y[0]]=tov[i],bz[tov[i]]=1;}mem(bz,0);for (int i=1;i<=Y[0];i++)bz[Y[i]]=1;ll sum=0;for (int ii=1,x;ii<=X[0];ii++){x=X[ii];for (int i=last[x];i;i=next[i])if (len[i]==0&&bz[tov[i]])sum+=len[i^1];}(sum==ans)?printf("Yes "):printf("No ");printf("%d\n",ans);}
}

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

相关文章

​如何高效开发一个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…

Ubuntu LTS 系统学习使用体会和实用工具软件汇总 6.04 8.04 10.04 12.04 14.04 16.04

Ubuntu LTS 系统学习体会和工具软件汇总 6.04 8.04 10.04 12.04 14.04 16.04 ubuntu入门必备pdf&#xff1a;http://download.csdn.net/detail/zhangrelay/9661749 最早接触Ubuntu是在10年前&#xff08;6.04&#xff09;&#xff0c;之前用过Red Hat&#xff08;fedora&…