JZOJ3348. 【NOI2013模拟】秘密任务

news/2024/5/20 20:18:53

Description

  • 给定无向图,有边权和点权,删去一条边的代价为这条边的任意一个顶点的权值,求一个最小代价的删边方案,使得1到n的在原图中的最短路都被断开。问最小代价,以及这个方案是否唯一。
  • 2 ≤ N ≤ 400, 1 ≤ M ≤ 4 00 0,1 ≤ T ≤ 5,1 ≤ Ai, c ≤ 10^9。无向图可能有重边 。

Solution(一些很显然的东西)

  • 显然建出最短路图,然后需要将最短路图割开,裸的最小割模型,有向边就是最短路图的边,流量为两个顶点点权最小值。跑网络流即可得出最小代价。
  • 怎么知道最小割是否唯一呢?
  • 首先简化模型:一条边的流量如果为顶点点权的min的话,还要讨论顶点的点权是否一样,再看一看这条边割了没有,这么多讨论十分难做,不如将这条边拆成两条边,一条边的流量为一个点的点权。
  • 然后我们运用必割边,如果必割边的流量之和小于最大流,那么剩下的部分一定由可能割的边组成,自然就没有唯一的方案了。
  • 问题来了,什么是必割边?

必割边(重点在这里)

  • 必割边就是任意一个最小割都存在的边。
  • 如果一条边的两个端点u,v分别能在残量网络中与S和T相连,那么这条边就是必割边。
  • 如果这条边(u,v)没有割的话,必然可以再从S到u到v到T再流一条过去,流量就会变大,就不满足最大流的性质 ,所以这条边一定是割掉了的。
  • 从S和T分别遍历一波残量网络流好了。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 405
#define maxm 8005
#define maxd 1005
#define maxt 9005
#define inf 1e18
#define I(i) ((i&1)?i+1:i-1)
#define ll long long 
using namespace std;int T,n,m,i,j,k,x,y,num;
int em,e[maxm*2],nx[maxm*2],ls[maxt],tot[maxn],to[maxn][maxm/2];
ll a[maxn],ec[maxm*2],to_c[maxn][maxm/2],z,dis[maxt],ans,sum;
int t,w,d[maxd],vis[maxt],bz[maxt];void SPFA(){memset(vis,0,sizeof(vis));memset(dis,127,sizeof(dis));t=0,w=1,d[1]=1,vis[1]=1,dis[1]=0;while (t<w){t=(t+1)%maxd; int x=d[t]; vis[x]=0;for(int i=1;i<=tot[x];i++) {int y=to[x][i];if (dis[x]+to_c[x][i]<dis[y]){dis[y]=dis[x]+to_c[x][i];if (!vis[y]) vis[y]=1,w=(w+1)%maxd,d[w]=y;}}}
}void insert(int x,int y,ll z){em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em]=z;em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; ec[em]=0;
}int BFS(int S,int T){memset(dis,127,sizeof(dis));t=0,w=1,d[1]=S,dis[S]=0;while (t<w){int x=d[++t];for(int i=ls[x];i;i=nx[i]) if (dis[x]+1<dis[e[i]]&&ec[i]){dis[e[i]]=dis[x]+1;d[++w]=e[i];}}return dis[T]<1e18;
}ll dfs(int x,ll p){if (x==n) return p;ll res=p;for(int i=ls[x];i&&res;i=nx[i]) if (dis[x]+1==dis[e[i]]&&ec[i]){ll tmp=dfs(e[i],min(res,ec[i]));res-=tmp;ec[i]-=tmp,ec[I(i)]+=tmp;}return p-res;
}ll dinic(){ll ans=0;while (BFS(1,n)){for(ll tmp=dfs(1,inf);tmp;tmp=dfs(1,inf))ans+=tmp;}return ans;
}void BFS2(int S){t=0,w=1,d[1]=S,bz[S]=1;while (t<w){int x=d[++t];for(int i=ls[x];i;i=nx[i]) if (!bz[e[i]]&&ec[i]){bz[e[i]]=1;d[++w]=e[i];}}
}void BFS3(int S){t=0,w=1,d[1]=S,bz[S]=2;while (t<w){int x=d[++t];for(int i=ls[x];i;i=nx[i]) if (!bz[e[i]]&&ec[I(i)]){bz[e[i]]=2;d[++w]=e[i];}}
}int main(){scanf("%d",&T);while (T--){scanf("%d%d",&n,&m);for(i=1;i<n;i++) scanf("%lld",&a[i]);a[n]=inf;memset(tot,0,sizeof(tot));for(i=1;i<=m;i++) {scanf("%d%d%lld",&x,&y,&z);tot[x]++,to[x][tot[x]]=y,to_c[x][tot[x]]=z;tot[y]++,to[y][tot[y]]=x,to_c[y][tot[y]]=z;}SPFA();em=0,memset(ls,0,sizeof(ls)),num=n;for(i=1;i<=n;i++) for(j=1;j<=tot[i];j++){k=to[i][j];if (dis[i]+to_c[i][j]==dis[k]){++num;insert(i,num,a[i]);insert(num,k,a[k]);}}ans=dinic();memset(bz,0,sizeof(bz));BFS2(1);BFS3(n);sum=0;for(x=1;x<=num;x++) for(i=ls[x];i;i=nx[i]) if (i&1&&bz[x]+bz[e[i]]==3)sum+=ec[i]+ec[I(i)];if (sum<ans) printf("No %lld\n",ans);else printf("Yes %lld\n",ans);}
}

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

相关文章

比亚迪、理想冒头背后,混动完胜纯电动?

进入六月份&#xff0c;各家车企的五月销量成绩陆续出炉了&#xff0c;差距也再次拉大。其中&#xff0c;比亚迪以23.9万辆的销售成绩再次夺得冠军&#xff0c;特斯拉中国则突破了单月7.5万辆&#xff0c;广汽埃安也首次突破了单月4.5万辆&#xff0c;上汽乘用车则上升至第四位…

bzoj 3258 秘密任务

http://www.elijahqi.win/archives/3689 Description Alice听说在一片神奇的大陆MagicLand&#xff0c;有一个古老的传说……很久很久以前&#xff0c;那个时候 MagicStates共和国刚刚 成立。 反对新政府的势力虽已被镇压&#xff0c;但仍然在暗地活动。这一次&#xff0c;情报…

秘密任务

秘密任务 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;进入…