Delivering Goods UVALive

Delivering Goods UVALive

Delivering Goods UVALive - 7986(最短路+最小路径覆盖)

题意：

给一张n个点m条边的有向带权图，给出C个关键点，问沿着最短路径走，从0最少需要出发多少次才能能覆盖这些关键点
(1 <= n <= 1000)
(1 <= m <= 10^5)
(1 <= w <= 10^9)
(1 <= C <= 300)

题解：

对所有的关键点建一个新图，对于任意两个关键点
若满足在原图中的最短路(dis(0,u)+dis(u,v)=dis(0,v)),
则(u)到(v)连一条有向边
显然新图一定是个(DAG),答案就等于新图的最小不相交路径覆盖

复习一下(DAG)上的最小不相交路径覆盖

对于一条路径，起点的入度为0，终点的出度为0，中间节点的出入度都为1每一个点最多只能有1个后继，同时每一个点最多只能有1个前驱。假如我们选择了一条边(u,v)，也就等价于把前驱u和后继v匹配上了。这样前驱u和后继v就不能和其他节点匹配。利用这个我们可以这样来构图：
将每一个点拆分成2个，分别表示它作为前驱节点和后继节点。将所有的前驱节点作为A部，所有后继节点作为B部，
若原图中存在一条边(u,v)，则连接A部的u和B部的v
然后跑二分图匹配,答案就是点数-最大匹配数,也可以这样理解，我们要让结尾结点尽可能少，所以就要尽可能多的配对
一个点既可能做为前驱也可能做为后继，所以需要拆点若求DAG上的可相交路径覆盖，求出图的floyd，转化为求不相交路径覆盖即可

#include<bits/stdc++.h>
#define LL long long
#define P pair<LL,int>
using namespace std;
const LL inf = 1e15;
const int N = 1e3 + 10;
vector<P> G[N];
vector<int> GG[N];
LL dis[N][N];
int n,m,C;
int a[N];
void dij(LL dis[],int s){for(int i = 0;i < n;i++) dis[i] = inf;dis[s] = 0;priority_queue<P,vector<P>,greater<P> >q;q.push(P(0,s));while(!q.empty()){P cur = q.top();q.pop();int u = cur.second;if(dis[u] < cur.first) continue;for(auto now:G[u]){int v = now.second;if(now.first + dis[u] < dis[v]){dis[v] = dis[u] + now.first;q.push(P(dis[v],v));}}}
}
int match[1000];
int vis[1000];
bool dfs(int u){vis[u] = 1;for(auto v:GG[u]){int w = match[v];if(w < 0 || !vis[w] && dfs(w)){match[v] = u;return true;}}return false;
}
int Maxmatch(){int ans = 0;memset(match, -1, sizeof(match));for(int i = 1;i <= C;i++){memset(vis,0,sizeof(vis));if(dfs(i)) ans++;}return ans;
}
int main(){int cas = 1;while(scanf("%d%d%d",&n,&m,&C)&&(n+m+C)){for(int i = 1;i <= C;i++) scanf("%d",a + i);for(int i = 0;i < n;i++) G[i].clear();for(int i = 0;i < m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);G[u].push_back(P(w,v));}dij(dis[0],0);for(int i = 1;i <= C;i++) GG[i].clear();for(int i = 1;i <= C;i++){int u = a[i];dij(dis[u],u);for(int j = 1;j <= C;j++){if(a[j] != u && dis[0][u] + dis[u][a[j]] == dis[0][a[j]]) GG[i].push_back(j + C);}}printf("Case %d: %dn",cas++,C - Maxmatch());}return 0;
}

转载于:.html