poj|poj 1364 King （差分约束） poj1364King（差分约束）

1364 -- King
继续差分约束的题。如果是“lt”就构造(s+n+1)->(s)=-w+1的边，否则构造(s)->(s+n+1)=w+1的边。因为没有取等号，所以w要加减一。
因为没有其他限制，所以不用别的附加边。
代码如下：

文章图片

文章图片

1 #include 2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 const int N = 111; 10 const int M = N * N; 11 const int INF = 0x55555555; 12 struct Edge { 13int u, v, nx, c; 14 } edge[M]; 15 int eh[N], ec; 16 17 void init() { 18memset(eh, -1, sizeof(eh)); 19ec = 0; 20 } 21 22 void addedge(int u, int v, int w) { 23edge[ec] = Edge{u, v, eh[u], w}; 24eh[u] = ec++; 25 } 26 27 int dis[N]; 28 bool bellman(int n) { 29for (int i = 1; i <= n; i++) dis[i] = -INF; 30dis[1] = 0; 31bool ok; 32for (int i = 0; i < n; i++) { 33ok = true; 34for (int j = 0; j < ec; j++) { 35if (dis[edge[j].v] < dis[edge[j].u] + edge[j].c) { 36dis[edge[j].v] = dis[edge[j].u] + edge[j].c; 37ok = false; 38} 39} 40if (ok) return true; 41} 42for (int j = 0; j < ec; j++) { 43if (dis[edge[j].v] < dis[edge[j].u] + edge[j].c) return false; 44} 45return true; 46 } 47 48 int main() { 49 //freopen("in", "r", stdin); 50int n, m; 51while (~scanf("%d%d", &n, &m) && n) { 52init(); 53int u, v, w; 54char op[3]; 55for (int i = 0; i < m; i++) { 56scanf("%d%d%s%d", &u, &v, op, &w); 57v += u + 1; 58if (op[0] == 'l') addedge(v, u, -w + 1); 59else addedge(u, v, w + 1); 60} 61if (bellman(n)) puts("lamentable kingdom"); 62else puts("successful conspiracy"); 63} 64return 0; 65 }

View Code
——written by Lyon
【poj|poj 1364 King （差分约束）】转载于:https://www.cnblogs.com/LyonLys/p/poj_1364_Lyon.html