poj2983

两张图片足矣说明问题。

任何形如上述约束条件的取值问题均可转化为差分约束问题。< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+1ti146O61LzK+M28tcS9qMGioaM8L3A+CjxwPtTaQXg8PUK1xM+1zbPW0KOsvattKm61xM/f0NS55ruuvtjV80G/tNf2ysduuPa94bXjus1tzPWx37XEzby1xMHavdO+2NXzoaPJz8281tCjrMO/uPa92rXjtcQmIzIwNTQwO8rHZGVsdGEodjAsdmkpo6zSsr7Nysd2MLW9dmm1xNfutszCt7XEJiMyMDU0MDuhozwvcD4KPHA+PHN0cm9uZz7P6s+4wLTLtaO6R6OoVqOsRaOpo6zKx9K7uPa0+Mio1ti1xNPQz/LNvKOsxuTW0Dwvc3Ryb25nPjwvcD4KPHA+PHN0cm9uZz5WPXt2MCx2MSx2MiwuLi4sdm59Ozwvc3Ryb25nPjwvcD4KPHA+PHN0cm9uZz5FPXsodmksdmopOnhqLXhpPD1ia31Veyh2MCx2MSksKHYwLHYyKSwuLi4odjAsdm4pfS48L3N0cm9uZz48L3A+CjxwPjxzdHJvbmc+xMfDtKOsPC9zdHJvbmc+PC9wPgo8cD48c3Ryb25nPjEuzbzW0NfUyLu+zbD8uqzSu7j2djCjrNPD09qxo9akzbzW0NbBydm6rNPQ0ru49rXjo6jPwsPmtPrC67XEs6y8ttS0teOjqaGjPC9zdHJvbmc+PC9wPgo8cD48c3Ryb25nPjIusd+8r0Ww/LqstcTKx8O/uPay7rfW1LzK+LXEsd+jrNTZvNPJz7Hfo6h2MKOsdmmjqaOsaT0xLDIsMywuLi4sbqGjyOe5+3hqLXhpPD1ia8rH0ru49rLut9bUvMr4zPW8/qOs1PKx3yh2aSx2aim1xMio1tjKx2JrLsv509C003Yws/a3orXEsd/IqNbYyscwoaM8L3N0cm9uZz48L3A+CjxwPrjDzOKjujwvcD4KPHA+y/nOvSBQIEEgQiBYIL/J0tTXqru7zqo8YnI+CkEtQj49eCAmYW1wOyZhbXA7IEEtQjw9WCA8PT4gQi1BIDw9IC1YICZhbXA7JmFtcDsgQS1CIDw9WDxicj4KtvggViBBIEIgPD0+IEE+PUImIzQzOzEgPD0+IEIgJiM0MzsgMSA8PUEgIDw9PiBCIC0gQSA8PSAtMaGjPGJyPgo8L3A+CjxwPsi7uvPM13NwZmG8tL/JwcuhozwvcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">#include #include #include #include #define MAXN 2000 #define MAX 999999999 using namespace std; int n, m; struct Tnode { int id, len; Tnode(int a, int b) : id(a), len(b) {} }; vector adj[MAXN]; int dis[MAXN], vis[MAXN]; bool hashtable[MAXN]; queue q; bool spfa() { memset(hashtable, false, sizeof(hashtable)); memset(vis, 0, sizeof(vis)); dis[0] = 0; while (!q.empty()) q.pop(); q.push(0); while (!q.empty()) { int now = q.front(); q.pop(); hashtable[now] = false; for (int i = 0; i < adj[now].size(); i++) { int v = adj[now][i].id; int cost = adj[now][i].len; if (dis[v] > dis[now] + cost) { dis[v] = dis[now] + cost; if (!hashtable[v]) { q.push(v); hashtable[v] = true; } if (++vis[v] >= n) return false; } } } return true; } int main() { while (cin>>n>>m) { for (int i = 0; i <= n; i++) { adj[i].clear(); dis[i] = MAX; } int a, b, c; char ch; for (int i = 0; i < m; i++) { cin>>ch; if (ch == 'P') { cin>>a>>b>>c; adj[b].push_back(Tnode(a, c)); adj[a].push_back(Tnode(b, -c)); } else { cin>>a>>b; adj[a].push_back(Tnode(b, -1)); } } for (int i = 0; i <= n; i++) adj[0].push_back(Tnode(i, 0)); if (!spfa()) cout << "Unreliable" << endl; else cout << "Reliable" << endl; } }