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: %d\n",cas++,C - Maxmatch());

    }

    return 0;

}

巴特西

Delivering Goods UVALive - 7986（最短路+最小路径覆盖）

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

题意：

题解：

最新文章

热门文章