BZOJ 3890 [Usaco2015 Jan]Meeting Time:拓扑图dp
阅读原文时间:2023年07月15日阅读:1

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3890

题意:

  给你一个有向图,n个点(n <= 100),m条边。

  且所有的边都是从编号小的点指向编号大的点。

  对于每条边i,Bessie要用c[i]的时间,Elsie要用d[i]的时间(c,d <= 100)。

  Bessie和Elsie从1号点出发,向n号点走去,且两人都不会在路上停留。

  问你使两人同时到达n点的最小时间。若不可能同时到达,输出"IMPOSSIBLE"。

题解:

  表示状态:

    bool f[i][j] and g[i][j]

    分别表示Bessie和Elsie是否能够同时到达i号点,且花费时间为j。

  找出答案:

    min i with f[n][i] and g[n][i]

    即两人同时到达n的最短时间

  如何转移:

    对于每个点i,一定是从某些编号比i小的点转移而来。

    所以从小到大枚举点i,然后枚举到达时间j,再枚举i能够到达的下一个点dst。

    顺推:

      f[dst][j+c] |= f[i][j]

      g[dst][j+d] |= g[i][j]

  边界条件:

    f[1][0] = g[1][0] = true

AC Code:

#include
#include
#include
#include
#define MAX_N 105
#define MAX_T 10005

using namespace std;

struct Edge
{
int dest;
int c;
int d;
Edge(int _dest,int _c,int _d)
{
dest=_dest;
c=_c;
d=_d;
}
Edge(){}
};

int n,m;
int ans=-;
int f[MAX_N][MAX_T];
int g[MAX_N][MAX_T];
vector edge[MAX_N];

void read()
{
cin>>n>>m;
int a,b,c,d;
for(int i=;i>a>>b>>c>>d;
edge[min(a,b)].push_back(Edge(max(a,b),c,d));
}
}

void solve()
{
memset(f,false,sizeof(f));
memset(g,false,sizeof(g));
f[][]=true;
g[][]=true;
for(int i=;i<=n;i++)
{
for(int j=;j<MAX_T;j++)
{
if(f[i][j] || g[i][j])
{
for(int k=;k<edge[i].size();k++)
{
Edge temp=edge[i][k];
f[temp.dest][j+temp.c]|=f[i][j];
g[temp.dest][j+temp.d]|=g[i][j];
}
}
}
}
for(int i=;i<MAX_T;i++)
{
if(f[n][i] && g[n][i])
{
ans=i;
break;
}
}
}

void print()
{
if(ans==-) cout<<"IMPOSSIBLE"<<endl;
else cout<<ans<<endl;
}

int main()
{
read();
solve();
print();
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章