POJ 1364 差分约束

发布时间:2016-12-10 22:45:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 1364 差分约束",主要涉及到POJ 1364 差分约束方面的内容,对于POJ 1364 差分约束感兴趣的同学可以参考一下。

判断差分约束是否存在 #include <set> #include <cmath> #include <queue> #include <stack> #include <string> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const double PI = acos(-1.0); template <class T> inline T MAX(T a, T b){if (a > b) return a;return b;} template <class T> inline T MIN(T a, T b){if (a < b) return a;return b;} const int N = 111; const int M = 11111; const LL MOD = 1000000007LL; const int dir[4][2] = {1, 0, -1, 0, 0, -1, 0, 1}; const int INF = 0x3f3f3f3f; struct edge { int x,y,d; }; edge a[101]; int d[101]; int main() { int m,n,i,j,k,x,y; string s; while(cin>>m&&m!=0) { cin>>n; for(i=1;i<=n;i++) { cin>>x>>y>>s>>k; if(s=="gt") { a[i].x=x+y; a[i].y=x-1; a[i].d=k+1; } else { a[i].x=x-1; a[i].y=x+y; a[i].d=-k+1; } } for(i=0;i<=m;i++) d[i]=-INF; bool circle; for(i=0;i<=m;i++) { circle=false; for(j=1;j<=n;j++) { if(d[a[j].y]+a[j].d>d[a[j].x]) { d[a[j].x]=d[a[j].y]+a[j].d; circle=true; } } } if(circle) cout<<"successful conspiracy"<<endl; else cout<<"lamentable kingdom"<<endl; } return 0; }

上一篇:hdu 3033 分组背包 每组至少选一个
下一篇:PPTP 理解以及报文的分析

相关文章

相关评论