[BZOJ3890] [Usaco 2015 Jan] 미팅 타임 토폴로지 단순DP

광고:

#include <stdio.h>
int main()
{
    puts("       [vmurder]  ");
    puts("  ：blog.csdn.net/vmurder/article/details/43971435");
}

제목:
n개의 점 m변의 유방향 무환도를 제시하고 각 변의 두 변권을 제시한다.n<=100, 무거운 테두리가 없습니다.그리고 두 개의 길이가 같고 가능한 한 짧은 경로를 요구한다. 경로 1은 첫 번째 변권을 사용하고 경로 2는 두 번째 변권을 사용한다.없으면 내보내기
문제 풀이:
단순 토폴로지 DPbool형 수조 f[i][j], g[i][j]는 i번째 점에 1이 점의 권한 값이 j인 경로 1, 2가 있는지 여부를 나타낸다.
코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;
bool f[N][N*N],g[N][N*N];
int map1[N][N],map2[N][N];
int n,m,stk[N],top,d[N];
int main()
{
// freopen("test.in","r",stdin);
    int i,j,k;
    int a,b,c;
    memset(map1,-1,sizeof map1);
    memset(map2,-1,sizeof map2);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d%d",&a,&b,&c,&k);
        map1[a][b]=c,map2[a][b]=k,d[b]++;
    }
    for(i=1;i<=n;i++)if(!d[i])stk[++top]=i;
    f[1][0]=g[1][0]=1;
    while(top)
    {
        a=stk[top--];
        for(i=1;i<=n;i++)if(map1[a][i]+1)
        {
            if(--d[i]==0)stk[++top]=i;
            for(j=map1[a][i];j<=10000;j++)f[i][j]|=f[a][j-map1[a][i]];
            for(j=map2[a][i];j<=10000;j++)g[i][j]|=g[a][j-map2[a][i]];
        }
    }
    for(i=0;i<=10000;i++)
    {
        if(f[n][i]&g[n][i])
        {
            printf("%d
",i);
            return 0;
        }
    }
    puts("IMPOSSIBLE");
    return 0;
}