HDU6252-Subway Chasing - wang_128的博客 - CSDN博客

文章价值(3) ?
阅读数(546) ?

Subway Chasing

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Time Limit: 6000/3000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Total Submission(s): 113????Accepted Submission(s): 27
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Special Judge


Problem Description
Mr. Panda and God Sheep are roommates and working in the same company. They always take subway to work together. There are?N?subway stations on their route, numbered from 1 to?N. Station 1 is their home and station?N?is the company.
One day, Mr. Panda was getting up later. When he came to the station, God Sheep has departed?X?minutes ago. Mr. Panda was very hurried, so he started to chat with God Sheep to communicate their positions. The content is when Mr. Panda is between station?A?and?B, God Sheep is just between station?C?and?D.
B?is equal to?A+1?which means Mr. Panda is between station?A?and?A+1?exclusive, or?B?is equal to?A?which means Mr. Panda is exactly on station?A. Vice versa for?C?and?D. What’s more, the communication can only be made no earlier than Mr. Panda departed and no later than God Sheep arrived.
After arriving at the company, Mr. Panda want to know how many minutes between each adjacent subway stations. Please note that the stop time at each station was ignored.
?

Input
The first line of the input gives the number of test cases,?T.?T?test cases follow.
Each test case starts with a line consists of 3 integers?N,?M?and?X, indicating the number of stations, the number of chat contents and the minute interval between Mr. Panda and God Sheep. Then?M?lines follow, each consists of 4 integers?A,?B,?C,?D, indicating each chat content.
1T30
1N,M2000
1X109
1A,B,C,DN
ABA+1
CDC+1
?

Output
For each test case, output one line containing “Case #x: y”, where?x?is the test case number (starting from 1) and?y?is the minutes between stations in format?t1,t2,...,tN?1.?ti?represents the minutes between station?i?and?i+1. If there are multiple solutions, output a solution that meets?0<ti2×109. If there is no solution, output “IMPOSSIBLE” instead.
?

Sample Input
2 4 3 2 1 1 2 3 2 3 2 3 2 3 3 4 4 2 2 1 2 3 4 2 3 2 3
?

Sample Output
Case #1: 1 3 1 Case #2: IMPOSSIBLE
Hint
In the second test case, when God Sheep passed the third station, Mr. Panda hadn’t arrived the second station. They can not between the second station and the third station at the same time.
?

Source
?


题意:有两个人坐地铁上班,地铁一共有n个站,一个人比另一个人早出发x分钟,他们一共交流了m次,每次他们互相报告各自的位置,找出一组可行解表示相邻两站需要的时间;若没有,输出IMPOSSIBLE

解题思路:因为两个人相距距离始终不变,所以可以列出一系列不等式,然后就是差分约束系统了


#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define LL long long
const int INF=0x3F3F3F3F;

int n,m;
LL x;
int u,uu,v,vv,vis[2009],tot[2009];
int s[2009],nt[200009],e[200009];
LL val[200009],dis[2009];

int spfa()
{
    memset(vis,0,sizeof vis);
    memset(dis,0,sizeof dis);
    memset(tot,0,sizeof tot);
    queueq;
    q.push(1);
    vis[1]=1;
    tot[1]++;
    while(!q.empty())
    {
        int pre=q.front();
        q.pop();
        vis[pre]=0;
        for(int i=s[pre];~i;i=nt[i])
        {
            if(dis[e[i]]=n+2) return 0;
                    vis[e[i]]=1;
                }
            }
        }
    }
    return 1;
}

int main()
{
    int t, cas = 1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%lld",&n,&m,&x);
        memset(s,-1,sizeof s);
        int cnt=1;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&u,&uu,&v,&vv);
            if(u==uu)
            {
                if(v==vv)
                {
                    if(u!=v) nt[cnt]=s[u],s[u]=cnt,e[cnt]=v,val[cnt++]=x;
                    if(u!=v) nt[cnt]=s[v],s[v]=cnt,e[cnt]=u,val[cnt++]=-x;
                }
                else
                {
                    if(u!=vv) nt[cnt]=s[u],s[u]=cnt,e[cnt]=vv,val[cnt++]=x+1;
                    if(u!=v) nt[cnt]=s[v],s[v]=cnt,e[cnt]=u,val[cnt++]=1-x;
                }
            }
            else
            {
                if(v==vv)
                {
                    if(u!=v) nt[cnt]=s[u],s[u]=cnt,e[cnt]=v,val[cnt++]=x+1;
                    if(uu!=v) nt[cnt]=s[v],s[v]=cnt,e[cnt]=uu,val[cnt++]=1-x;
                }
                else if(u==v&&u!=vv) nt[cnt]=s[u],s[u]=cnt,e[cnt]=vv,val[cnt++]=x+1;
                else
                {
                    if(vv!=u) nt[cnt]=s[u],s[u]=cnt,e[cnt]=vv,val[cnt++]=x+1;
                    if(uu!=v) nt[cnt]=s[v],s[v]=cnt,e[cnt]=uu,val[cnt++]=1-x;
                }
            }
        }
        for(int i=2;i<=n;i++)
            nt[cnt]=s[i-1],s[i-1]=cnt,e[cnt]=i,val[cnt++]=1;
        int flag=spfa();
        printf("Case #%d:", cas++);
        if(!flag) printf(" IMPOSSIBLE\n");
        else
        {
            for(int i=2;i<=n;i++) printf(" %lld",dis[i]-dis[i-1]);
            printf("\n");
        }
    }
    return 0;
}




(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: