[最小割][spfa][tarjan] Jzoj P3348 秘密任务

ゞ浴缸里的玫瑰 2021-11-02 10:20 286阅读 0赞

#### Description ####

![Image 1][]

#### Input ####

输入文件为secret.in ：  
  
第一行 包含一 个正整数 T，表示有 T组测试数据。接下来 依次是 T组测试数 据。  
  
每组测试数 据的第一行包含两个整N、M。  
  
第二行包含 N - 1个正整数，依次表示 A1，A2， …，AN-1。  
  
接下来 M行，每 行为三个 整数： ui、vi、ci，表示一条连接城市ui和城市 vi的路程等于 ci的高速公路。

#### Output ####

输出文件为 secret.out 。  
  
输出 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。无向图可能 有重边 。

# 题解 #

*  这简直就是码农题，很少在比赛中切掉码农题了
 *  先在原图里跑一遍最短路，然后把不在最短路里的边删掉
 *  把其他的边，拆成起点和终点两个点，每个点为该点的点权，跑一遍最大流，这就是第一问
 *  对于第二问，我们就是要最小割的唯一性判定
 *  跑一遍tarjan对于一条满流边
 *  如果起点与终点分属两个scc，那么它可以作为原图最小割的一条边
 *  而当起点与S所在scc相同，终点与T所在scc相同时，这条边的选择是唯一的

# 代码 #

1 #include <cstdio>
      2 #include <iostream>
      3 #include <cstring>
      4 #define N 410
      5 #define M 8010
      6 #define P 100010
      7 #define ll long long 
      8 using namespace std;
      9 int n,m,T,cnt,tot,Scc,flag,top,p,q,s,t,head[N],last[N],cur[N],vis[N],Q[P],dfn[N],low[N],scc[N],val[N],stack[N];
     10 ll ans,dis[N];
     11 struct edge { int to,from,v,pre; }e[M],E[M*2];
     12 void insert(int x,int y,int v)
     13 {
     14     e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt,e[cnt].v=v;
     15     e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt,e[cnt].v=v;
     16 }
     17 void ins(int x,int y,int v)
     18 {
     19     E[++tot].to=y,E[tot].pre=x,E[tot].v=v,E[tot].from=last[x],last[x]=tot;
     20     E[++tot].to=x,E[tot].pre=y,E[tot].v=0,E[tot].from=last[y],last[y]=tot;
     21 }
     22 void spfa()
     23 {
     24     memset(dis,0x3f,sizeof(dis)),memset(vis,0,sizeof(vis));
     25     dis[1]=0,p=0,Q[q=1]=1,vis[1]=1;
     26     while (p!=q)
     27     {
     28         int u=Q[(++p)%P]; vis[u]=0;
     29         for (int i=head[u];i;i=e[i].from)
     30             if (dis[e[i].to]>dis[u]+e[i].v)
     31             {
     32                 dis[e[i].to]=dis[u]+e[i].v;
     33                 if (!vis[e[i].to]) vis[e[i].to]=1,Q[(++q)%P]=e[i].to;
     34             }
     35     }
     36 }
     37 void add(int x)
     38 {
     39     if (vis[x]) return;
     40     vis[x]=1;
     41     for (int i=head[x];i;i=e[i].from) if (dis[x]==dis[e[i].to]+e[i].v) ins(e[i].to,x,min(val[x],val[e[i].to])),add(e[i].to);
     42 }
     43 bool bfs()
     44 {
     45     memset(dis,-1,sizeof(dis)),p=q=0;
     46     Q[++q]=s,dis[s]=1;
     47     while (p<q)
     48     {
     49         int u=Q[++p];
     50         for (int i=last[u];i;i=E[i].from)
     51             if (E[i].v&&dis[E[i].to]==-1)
     52             {
     53                 dis[E[i].to]=dis[u]+1,Q[++q]=E[i].to;
     54                 if (t==E[i].to) return 1; 
     55             }
     56     }
     57     return 0;
     58 }
     59 int dfs(int x,ll maxf)
     60 {
     61     if (x==t) return maxf;
     62     ll f=0,r;
     63     for (int i=cur[x];i;i=E[i].from)
     64     {
     65         cur[x]=i;
     66         if (E[i].v&&dis[E[i].to]==dis[x]+1)
     67         {
     68             r=dfs(E[i].to,min(maxf-f,(ll)E[i].v)),E[i].v-=r,E[i^1].v+=r,f+=r;
     69             if (f==maxf) break;
     70         }
     71     }
     72     if (!f) dis[x]=-1;
     73     return f;
     74 }
     75 ll dinic()
     76 {
     77     ll r=0;
     78     while (bfs()) memcpy(cur,last,sizeof(cur)),r+=dfs(s,1ll<<60);
     79     return r;
     80 }
     81 void tarjan(int x)
     82 {
     83     dfn[x]=low[x]=++dfn[0],stack[++top]=x;
     84     for (int i=last[x];i;i=E[i].from)
     85         if (E[i].v)
     86         {
     87             if (!dfn[E[i].to]) tarjan(E[i].to),low[x]=min(low[x],low[E[i].to]);
     88             else if (!scc[E[i].to]) low[x]=min(low[x],dfn[E[i].to]);
     89         }
     90     if (dfn[x]==low[x])
     91     {
     92         Scc++;
     93         for (int i;i!=x;) i=stack[top--],scc[i]=Scc;
     94     }
     95 }
     96 int main()
     97 {
     98     for (scanf("%d",&T);T;T--)
     99     {
    100         tot=1,cnt=flag=Scc=top=0,memset(head,0,sizeof(head)),memset(last,0,sizeof(last)),memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),memset(scc,0,sizeof(scc));
    101         scanf("%d%d",&n,&m);
    102         for (int i=1;i<n;i++) scanf("%d",&val[i]); val[n]=1<<30;
    103         for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),insert(x,y,z);
    104         spfa(),s=1,t=n,add(n),ans=dinic();
    105         for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
    106         for (int i=2;i<=tot;i+=2)
    107             if (!E[i].v)
    108             {
    109                 if (scc[E[i].pre]!=scc[E[i].to]&&!(scc[E[i].pre]==scc[1]&&scc[E[i].to]==scc[n])) flag=1;
    110                 if (scc[E[i].pre]==scc[1]&&scc[E[i].to]==scc[n]&&val[E[i].pre]==val[E[i].to]) flag=1; 
    111             }
    112         !flag?printf("Yes "):printf("No "); printf("%lld\n",ans);
    113     }
    114 }

转载于:https://www.cnblogs.com/Comfortable/p/11164729.html

[Image 1]: