Problem 1406 最小路径覆盖

来自NEUACM WIKI
跳转到: 导航, 搜索

1406 Repair Streets 最小路径覆盖 月赛H题

看上去题目很复杂。 实际上,可以转化为这样的一副图:

以时间为节点,如果这个节点u的task任务结束并且加上两个城市的路程时间后,依然能在另一个任务节点v开始前抵达,就脸上一条从u到v的有向路。

最后问题就转换为:输出最少的路径数目使之能遍历所有时间节点。

这就是最为常见的最小路径覆盖问题,最小路径覆盖一般为二分图来解,可以自行搜索相关资料。

#include<cstdio>
#include<cstring>
#include<memory.h>
using namespace std;
int Q,M;
int n;
int C[50][50];
struct Node{
    int id,s,time;
    Node(){};
    Node(int _id,int _s,int _time){id=_id;s=_s;time=_time;}
}; //task
 
struct Node T[1111];
int map[800][800];
int v[1001],set[1001];
int dfs(int k)
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(!v[i]&&map[k][i])
        {
            v[i]=1;
            if(dfs(set[i])||set[i]==0)
            {
                set[i]=k;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d %d",&Q,&M)!=EOF)
    {
        for(int i=1;i<=Q;i++)
            for(int j=1;j<=Q;j++)
                scanf("%d",&C[i][j]);
        for(int i=1;i<=M;i++){
            scanf("%d %d %d",&T[i].id,&T[i].s,&T[i].time);
        }
        memset(map,0,sizeof(map));
        memset(set,0,sizeof(set));
        for(int i=1;i <=M;i++)
            for(int j=1;j <=M;j++){
                if(T[i].s+T[i].time+C[T[i].id][T[j].id] <= T[j].s)
                    map[i][j]=1;
            }
        int ans = 0;
        n = M;
        for(int i = 1;i <= M;i++){
            memset(v,0,sizeof(v));
            if(dfs(i))ans++;
        }
        printf("%d\n",n-ans);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1406
    User: ipqhjjybj
    Language: C++
    Result: 正确
    Time:146 ms
    Memory:3316 kb
****************************************************************/
个人工具
名字空间

变换
操作
导航
工具箱