HDU 2448 Mining Station on the Sea

题意：有N艘船和N个港口，M个station。现在N艘船分别处在一些station上。有K条边连接站，有P条边连接港口和站。现在这N艘船都要回到港口，且每个港口只能容纳一艘船。问使这N艘船回到港口行程之和的最小值是多少。

比较明显的求最小权匹配，用KM。做最短路的时候要注意如果船已经回到港口了，就不能再跑出去了，所以做floyd闭包或其他最短路的时候，松弛的时候不能用港口去松弛一个点对。然后得到各个船所在位置到各个港口的最短路后，把边权赋成负的船到港口的最短路值，然后跑KM就可以了。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define maxn 105
  6 #define INF 1<<30
  7 using namespace std;
  8 
  9 struct KM{
 10     vector<int> G[maxn];
 11     int W[maxn][maxn],n;
 12     int Lx[maxn],Ly[maxn];
 13     int left[maxn];
 14     bool S[maxn],T[maxn];
 15 
 16     void init(int n)
 17     {
 18         this->n = n;
 19         for(int i = 0;i < n;i++)    G[i].clear();
 20         memset(W,0,sizeof(W));
 21     }
 22 
 23     void add_edge(int u,int v,int w)
 24     {
 25         G[u].push_back(v);
 26         W[u][v] = w;
 27     }
 28 
 29     bool match(int i)
 30     {
 31         S[i] = true;
 32         for(int k = 0;k < G[i].size();k++)
 33         {
 34             int j = G[i][k];
 35             if(Lx[i] + Ly[j] == W[i][j] && !T[j])
 36             {
 37                 T[j] = true;
 38                 if(left[j] == -1 || match(left[j]))
 39                 {
 40                     left[j] = i;
 41                     return true;
 42                 }
 43             }
 44         }
 45         return false;
 46     }
 47     void update()
 48     {
 49         int a = INF;
 50         for(int i = 0;i < n;i++)    if(S[i])
 51             for(int k = 0;k < G[i].size();k++)
 52             {
 53                 int j = G[i][k];    if(!T[j])
 54                 a = min(a,Lx[i] + Ly[j] - W[i][j]);
 55             }
 56         for(int i = 0;i < n;i++)
 57         {
 58             if(S[i])    Lx[i] -= a;
 59             if(T[i])    Ly[i] += a;
 60         }
 61     }
 62 
 63     void solve()
 64     {
 65         for(int i = 0;i < n;i++)
 66         {
 67             Lx[i] = *max_element(W[i],W[i]+n);
 68             left[i] = -1;
 69             Ly[i] = 0;
 70         }
 71         for(int i = 0;i < n;i++)
 72         {
 73             while(1)
 74             {
 75                 for(int j = 0;j < n;j++)    S[j] = T[j] = 0;
 76                 if(match(i))    break;
 77                 else            update();
 78             }
 79         }
 80     }
 81 };
 82 KM solver;
 83 int d[310][310];
 84 int pos[105];
 85 
 86 int main(){
 87     int n,m,k,p;
 88     while(scanf("%d%d%d%d",&n,&m,&k,&p) != EOF){
 89         for(int i = 1;i <= n;i++)   scanf("%d",&pos[i]);
 90 
 91         for(int i = 1;i <= m+n;i++)
 92         for(int j = 1;j <= m+n;j++){
 93             if(i != j)  d[i][j] = -1;
 94             else    d[i][j] = 0;
 95         }
 96 
 97         for(int i = 0;i < k;i++){
 98             int a,b,c;
 99             scanf("%d%d%d",&a,&b,&c);
100             d[a][b] = d[b][a] = d[a][b] == -1 ? c : min(c,d[a][b]);
101         }
102 
103         for(int i = 0;i < p;i++){
104             int a,b,c;
105             scanf("%d%d%d",&a,&b,&c);
106             d[m+a][b] = d[b][m+a] = d[m+a][b] == -1 ? c : min(c,d[m+a][b]);
107         }
108 
109         for(int k = 1;k <= m;k++)
110         for(int i = 1;i <= m+n;i++) if(d[i][k] != -1)
111         for(int j = 1;j <= m+n;j++) if(d[k][j] != -1 && (d[i][j] == -1 || d[i][j] > d[i][k] + d[k][j]))
112         d[i][j] = d[i][k] + d[k][j];
113 
114         solver.init(n);
115 
116         for(int i = 1;i <= n;i++)
117         for(int j = 1;j <= n;j++)
118         if(d[pos[i]][m+j] != -1)
119         solver.add_edge(i-1,j-1,-d[pos[i]][m+j]);
120 
121         solver.solve();
122 
123         int ans = 0;
124         for(int i = 0;i < n;i++)
125         ans -= solver.W[solver.left[i]][i];
126         printf("%d
",ans);
127     }
128     return 0;
129 }

View Code