HDU 3488-Tour KM

妖狐艹你老母 2023-10-11 09:33 7阅读 0赞

为什么可以这样拆点在 [这道题][Link 1] 都已经证明过

代码：

1 //题目上面说了“The only exception is that the first and the last city should be the same and this city is visited twice.”
      2 //我还以为是起点要使用两次，没想到题意就是全部点连接之后出入度都为1
      3 
      4 //题意：有n座城市，m条带权有向边。有人想要游历所有城市，于是制定了计划：游历的路径是一个或者多个环,且所有城市都必须仅存在于一个环中。问怎样设计路线使得总路程最短？
      5 //我们可以用最大权匹配去求：
      6 //1.对于每个点u，我们拆成u和u'。u代表着出点，在二分图的左侧；u'代表着入点，在二分图的右侧。
      7 //2.如果有一条有向边u-->v，那么在二分图中，我们加一条边u-->v'，并且权值取反。
      8 //
      9 //3.利用KM()算法，求出最大权匹配，再将结果取反，即为答案。
     10 // 举个三个点的例子
     11 // p->q`->q->r`->r->p`
     12 //
     13 //问：为何KM()算法求出来的就一定是一个或多个环呢？
     14 //1.可知，题目已经说明了必定有解。那么对应的二分图必定存在完全匹配，完全匹配也必定是最大匹配。
     15 //2.我们用KM()算法求出了最大权匹配。根据性质：最大权匹配必定为最大匹配。所以，如果最大匹配是完全匹配，那么最大权匹配也是完全匹配。
     16 //3.因为最大权匹配是完全匹配。所以所求出的解必定是一个或多个环。
     17 #include<stdio.h>
     18 #include<algorithm>
     19 #include<string.h>
     20 #include<iostream>
     21 #include<queue>
     22 #include<vector>
     23 using namespace std;
     24 const int maxn=510;
     25 const int INF=0x3f3f3f3f;
     26 int n,m;
     27 int g[maxn][maxn],link[maxn],matchx[maxn],matchy[maxn];
     28 int slack[maxn],visitx[maxn],visity[maxn];
     29 int dfs(int x)
     30 {
     31     visitx[x]=1;
     32     for(int i=1;i<=n;++i)
     33     {
     34         if(visity[i]) continue;
     35         int temp=matchx[x]+matchy[i]-g[x][i];
     36         if(temp==0)
     37         {
     38             visity[i]=1;
     39             if(link[i]==-1 || dfs(link[i]))
     40             {
     41                 link[i]=x;
     42                 return 1;
     43             }
     44         }
     45         else slack[i]=min(slack[i],temp);
     46     }
     47     return 0;
     48 }
     49 int km()
     50 {
     51     memset(link,-1,sizeof(link));
     52     memset(matchy,0,sizeof(matchy));
     53     for(int i=1;i<=n;++i)
     54     {
     55         matchx[i]=-INF;
     56         for(int j=1;j<=n;++j)
     57         {
     58             matchx[i]=max(matchx[i],g[i][j]);
     59         }
     60     }
     61     for(int x=1;x<=n;++x)
     62     {
     63         for(int i=1;i<=n;++i)
     64             slack[i]=INF;
     65         while(1)
     66         {
     67             memset(visitx,0,sizeof(visitx));
     68             memset(visity,0,sizeof(visity));
     69             if(dfs(x)) break;
     70             int d=INF;
     71             for(int i=1;i<=n;++i)
     72                 if(!visity[i])
     73                     d=min(d,slack[i]);
     74             for(int i=1;i<=n;++i)
     75             {
     76                 if(visitx[i])
     77                     matchx[i]-=d;
     78             }
     79             for(int i=1;i<=n;++i)
     80             {
     81                 if(visity[i]) matchy[i]+=d;
     82                 else slack[i]-=d;
     83             }
     84         }
     85     }
     86     int ans=0;
     87     for(int i=1;i<=n;++i)
     88     {
     89         if(link[i]!=-1)
     90             ans+=g[link[i]][i];
     91     }
     92     return ans;
     93 }
     94 int main()
     95 {
     96     int t;
     97     scanf("%d",&t);
     98     while(t--)
     99     {
    100         scanf("%d%d",&n,&m);
    101         memset(g,0,sizeof(g));
    102         for(int i=1;i<=n;++i)
    103         {
    104             for(int j=1;j<=n;++j)
    105             {
    106                 g[i][j]=-INF;
    107             }
    108         }
    109         while(m--)
    110         {
    111             int u,v,w;
    112             scanf("%d%d%d",&u,&v,&w);
    113             g[u][v]=max(-w,g[u][v]);
    114         }
    115         printf("%d\n",-km());
    116     }
    117     return 0;
    118 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11494098.html

[Link 1]: https://www.cnblogs.com/kongbursi-2292702937/p/11493957.html