uvalive 4885 差分约束

就是差分约束的裸题，因为今天比赛时间来不及，没搞完。

贴个模板。具体关于差分约束系统的解释请搜其他博客。

我用最长路和最短路都实现了一遍。

对于(>=)的系统，求最长路。

对于(<=)的系统，求最短路。

然后SPFA之前，我们可以将所有的点都入队。这样就相当于一个超级源点了。

最长路：

#include <set>  
#include <map>  
#include <stack>  
#include <cmath>  
#include <queue>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <iomanip>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 0x3fffffff  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair<int,int>  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
  
using namespace std ;  
  
#define N 1111  
vector<PII> G[N] ;  
int dis[N] , vis[N] ;  
int n , m ;  
queue<int>qe ;  
int cnt[N] ;  
void spfa() {  
    while(!qe.empty())qe.pop() ;  
    for (int i = 1 ; i <= n ; i ++ )dis[i] = 1 , vis[i] = 1 , qe.push(i) ;  
    mem(cnt ,0) ;  
    while(!qe.empty()) {  
        int tp = qe.front() ;  
        qe.pop() ;  
        vis[tp] = 0 ;  
        if(cnt[tp] > n) {  
            puts("Impossible.") ;  
            return ;  
        }  
        int sz = G[tp].size() ;  
        for (int i = 0 ; i < sz ; i ++ ) {  
            int e = G[tp][i].FI ;  
            int l = G[tp][i].SE ;  
            if(dis[e] < dis[tp] + l) {  
                dis[e] = dis[tp] + l ;  
                if(!vis[e]) {  
                    vis[e] = 1 ;  
                    qe.push(e) ;  
  
                    cnt[e] ++ ;  
                }  
            }  
        }  
    }  
    int mx = inf ;  
    for (int i = 1 ; i <= n ; i ++ ){  
        mx = min(dis[i] , mx) ;  
//        if(dis[i] >= 1000000){  
//            puts("Impossible.");return ;  
//        }  
    }  
    for (int i = 1 ; i <= n ; i ++ ){  
        dis[i] -= mx - 1 ;  
    }  
    for (int i = 1 ; i <= n ; i ++ ){  
        if(dis[i] >= 1000000){  
            puts("Impossible.") ; return ;  
        }  
    }  
    for (int i = 1 ; i < n ; i ++ )printf("%d ",dis[i]) ;  
    cout << dis[n] << endl;  
}  
char a[1111][111] ;  
int main() {  
    while(cin >> n , n) {  
        for (int i = 1 ; i <= n ; i ++ )G[i].clear() ;  
        cin >> m ;  
        int s , e , l ;  
        for (int i = 0 ; i < m ; i ++ ) {  
            scanf("%s %d %s %s",a[1] , &s , a[2] , a[3]) ;  
            if(a[3][0] == 'a'){  
                scanf("%s %d %s %s %s %s %d",a[1],&l ,a[1],a[1],a[1],a[1] ,&e) ;  
                G[e].push_back(mp(s , l)) ;  
            }  
            else {  
                scanf("%d %s %s %s %s %s %s %s %d",&l ,a[1] ,a[1],a[1],a[1],a[1],a[1],a[1] , &e) ;  
                G[e].push_back(mp(s, 0)) ;  
                G[s].push_back(mp(e, -l)) ;  
            }  
        }  
        spfa() ;  
    }  
    return 0 ;  
}

最短路：

#include <set>  
#include <map>  
#include <stack>  
#include <cmath>  
#include <queue>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <iomanip>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 0x3fffffff  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair<int,int>  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
  
using namespace std ;  
  
#define N 1111  
vector<PII> G[N] ;  
int dis[N] , vis[N] ;  
int n , m ;  
queue<int>qe ;  
int cnt[N] ;  
void spfa() {  
    while(!qe.empty())qe.pop() ;  
    for (int i = 1 ; i <= n ; i ++ )dis[i] = inf , vis[i] = 1 , qe.push(i) ;  
    mem(cnt ,0) ;  
    while(!qe.empty()) {  
        int tp = qe.front() ;  
        qe.pop() ;  
        vis[tp] = 0 ;  
        if(cnt[tp] > n) {  
            puts("Impossible.") ;  
            return ;  
        }  
        int sz = G[tp].size() ;  
        for (int i = 0 ; i < sz ; i ++ ) {  
            int e = G[tp][i].FI ;  
            int l = G[tp][i].SE ;  
            if(dis[e] > dis[tp] + l) {  
                dis[e] = dis[tp] + l ;  
                if(!vis[e]) {  
                    vis[e] = 1 ;  
                    qe.push(e) ;  
  
                    cnt[e] ++ ;  
                }  
            }  
        }  
    }  
    int mx = inf ;  
    for (int i = 1 ; i <= n ; i ++ ){  
        mx = min(dis[i] , mx) ;  
//        if(dis[i] >= 1000000){  
//            puts("Impossible.");return ;  
//        }  
    }  
    for (int i = 1 ; i <= n ; i ++ ){  
        dis[i] -= mx - 1 ;  
    }  
    for (int i = 1 ; i <= n ; i ++ ){  
        if(dis[i] >= 1000000){  
            puts("Impossible.") ; return ;  
        }  
    }  
    for (int i = 1 ; i < n ; i ++ )printf("%d ",dis[i]) ;  
    cout << dis[n] << endl;  
}  
char a[1111][111] ;  
int main() {  
    while(cin >> n , n) {  
        for (int i = 1 ; i <= n ; i ++ )G[i].clear() ;  
        cin >> m ;  
        int s , e , l ;  
        for (int i = 0 ; i < m ; i ++ ) {  
            scanf("%s %d %s %s",a[1] , &s , a[2] , a[3]) ;  
            if(a[3][0] == 'a'){  
                scanf("%s %d %s %s %s %s %d",a[1],&l ,a[1],a[1],a[1],a[1] ,&e) ;  
//                G[e].push_back(mp(s , l)) ;  
                G[s].push_back(mp(e , -l)) ;  
            }  
            else {  
                scanf("%d %s %s %s %s %s %s %s %d",&l ,a[1] ,a[1],a[1],a[1],a[1],a[1],a[1] , &e) ;  
//                G[e].push_back(mp(s, 0)) ;  
//                G[s].push_back(mp(e, -l)) ;  
                G[e].push_back(mp(s , l)) ;  
                G[s].push_back(mp(e , 0)) ;  
            }  
        }  
        spfa() ;  
    }  
    return 0 ;  
}

补充：软件开发 , C++ ,