当前位置: 首页 > 工具软件 > Subway > 使用案例 >

HDU6254 Subway Chasing

袁运良
2023-12-01

https://vjudge.net/contest/400914#problem/J
差分约束系统,设 T i T_i Ti是到达 i i i站的时刻,则 T i − T i − 1 > = 1 T_i-T_{i-1}>=1 TiTi1>=1
对于每个条件,若 a = = b & & c = = d a==b\&\&c==d a==b&&c==d,则 T d − T b = = 1 T_d-T_b==1 TdTb==1,否则 T d − T a > X & & T c − T b < X T_d-T_a>X\&\&T_c-Tb<X TdTa>X&&TcTb<X
据此建图,再加一个超级源,连到每个点,边权为0,使图连通,跑一遍spfa,若有负环,则失败,否则可行。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+100;
const int INF=0x3f3f3f3f;

int T,n,m,x;
int d[maxn],inq[maxn],cnt[maxn];
struct Edge{
    int to,dist;
};
vector<Edge> edges;
vector<int> G[maxn];

bool SPFA(int s)
{
    queue<int>Q;
    memset(inq,0,sizeof(inq));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;
    inq[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        inq[u]=false;
        for(int i=0;i<G[u].size();i++)
        {
            Edge& e=edges[G[u][i]];
            if(d[u]<INF && d[e.to]>d[u]+e.dist)
            {
                d[e.to]=d[u]+e.dist;
                if(!inq[e.to])
                {
                    Q.push(e.to);
                    inq[e.to]=1;
                    if(++cnt[e.to]>n)return false;
                }
            }
        }
    }
    return true;
}

void AddEdge(int a,int b,int c)
{
    edges.push_back((Edge){b,c});
    G[a].push_back(edges.size()-1);
}

int main()
{
	//freopen("input.in","r",stdin);
    cin>>T;
    for(int kase=1;kase<=T;kase++)
    {
        cin>>n>>m>>x;
        edges.clear();
        for(int i=1;i<=n;i++)G[i].clear();
		for(int i=1;i<=n;i++)AddEdge(0,i,0);
        for(int i=2;i<=n;i++)AddEdge(i,i-1,-1);
        for(int i=1;i<=m;i++)
        {
            int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
            if(a==b&&c==d)AddEdge(c,a,-x),AddEdge(a,c,x);
            else AddEdge(d,a,-x-1),AddEdge(b,c,x-1);
        }
        if(!SPFA(0))printf("Case #%d: IMPOSSIBLE\n",kase);
        else
        {
            printf("Case #%d:",kase);
            for(int i=2;i<=n;i++)printf(" %d",d[i]-d[i-1]);
            putchar('\n');
        }
    }
    return 0;
}

 类似资料:

相关阅读

相关文章

相关问答