P3116 [USACO15JAN]约会时间Meeting Time 拓扑排序
考虑dp,其中f1[i][j]表示由起点到达i,走的是路径1,路径总长度为j的方法可不可行,f2类似,拓扑排序的过程中大力转移即可。
转移过程类似背包问题。
好像可以用bitset优化,少一些常数。
注意输出IMPOSSIBLE!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| #include <bits/stdc++.h> #define MAXN 105 #define MAXE 10005 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } struct Edge{ int to,l1,l2; }; vector<Edge>G[MAXN]; int in[MAXN]; inline void AddEdge(int u,int v,int l1,int l2){ in[v]++; Edge temp; temp.to=v; temp.l1=l1; temp.l2=l2; G[u].push_back(temp); } int f1[MAXN][MAXE],f2[MAXN][MAXE]; int main(){ int n=read(),m=read(); for (register int i=1;i<=m;++i){ int u=read(),v=read(),l1=read(),l2=read(); AddEdge(u,v,l1,l2); } queue<int>Q; for (register int i=1;i<=n;++i){ if (!in[i]) Q.push(i); } f1[1][0]=f2[1][0]=true; while (Q.size()){ int u=Q.front();Q.pop(); for (register int i=0;i<G[u].size();++i){ int v=G[u][i].to,l1=G[u][i].l1,l2=G[u][i].l2; in[v]--; for (register int j=0;j<MAXE;++j){ if (j+l1<MAXE) f1[v][j+l1]|=f1[u][j]; if (j+l2<MAXE) f2[v][j+l2]|=f2[u][j]; } if (!in[v]) { Q.push(v); } } } for (register int i=0;i<MAXE;++i){ if (f1[n][i]&&f2[n][i]) { printf("%d\n",i); return 0; } } printf("IMPOSSIBLE"); }
|