题解 P3116 【[USACO15JAN]约会时间Meeting Time】

· · 题解

即将退役的选手来写篇题解

此题做法：拓扑排序 + DP

首先，根据题意我们可以得出，这是一张有向无环图（DAG），那我们也不难想到拓扑排序，同时做一遍 DP 。

由于数据范围比较小，可以设计出如下的 DP 模型-：

状态： f[i][j] 表示经过 j 时间能否到达 i 号结点；

转移方程： f[v][j]=f[u][j-edge[i].w]\ (j-edge[i].w\geq 0,(u,v)\in G)

边界： f[1][0]=1

目标状态： \min\{ j \},\ \text{s.t.}\ f[n][j]=1

注意到有两个人要走，所以我们开两个 DP 数组进行转移。最后求出最小的 j ，使得 f1[n][j]=f2[n][j]=1即可。

具体实现请看代码： 

#include <cstdio>
#include <queue> 
#define rint register int //卡常加速
#define MAXN 105
using namespace std;
queue <int> q; //用队列进行拓扑排序
int n,m,cnt,head[MAXN],ind[MAXN]; 
//n:结点数 m：边数 head,cnt：链式前向星存图用 ind: 存储结点入度
bool f1[MAXN][MAXN*MAXN],f2[MAXN][MAXN*MAXN];  
  //DP数组
struct Edge{
    int next,to,w1,w2;
}edge[MAXN*MAXN];
  //链式前向星，w1、w2分别存储两个人走这条边所需的时间
inline void add(int u,int v,int w1,int w2){
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].w1=w1;
    edge[cnt].w2=w2;
    head[u]=cnt;
} //加边
int main(){
    scanf("%d %d",&n,&m);
    for(rint i=1;i<=m;++i){
        int u,v,w1,w2;
        scanf("%d %d %d %d",&u,&v,&w1,&w2);
        add(u,v,w1,w2); //加边
        ++ind[v]; //统计入度
    }
    for(rint i=1;i<=n;++i)
        if(!ind[i]) q.push(i); //入度为0的点入队
    f1[1][0]=f2[1][0]=1; //DP边界
    while(!q.empty()){ //拓扑排序板子
        int u=q.front();
        q.pop();
        for(rint i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            for(rint j=0;j<=10000;++j){
                if(j-edge[i].w1>=0) f1[v][j]|=f1[u][j-edge[i].w1]; //转移，注意判断j-edge[i].w>=0 
                if(j-edge[i].w2>=0) f2[v][j]|=f2[u][j-edge[i].w2];
            }
            if(--ind[v]==0) q.push(v);
        }
    }
    for(rint i=0;i<=10000;++i)
        if(f1[n][i]&&f2[n][i]){
            printf("%d",i); //输出
            return 0;
        }
    printf("IMPOSSIBLE"); //判断无解情况
    return 0;
}