Hdu-6252 2017CCPC-Final J.Subway Chasing 差分约束

题意:有2个人,都去坐地铁,但是他们相差了X分钟,但是他们也一直在通讯,于是你就知道,你在AB站点中间的时候,他在CD中间,(B一定等于A+1或者A,同理D也是),问你每2个站之间需要的时间的一种方案使得满足上面那些话,满足不了输出IMPOSSIBLE.(站台从1到N,N<=2000)

题解:典型的差分约束我们回忆一下,对于不等式a-b<=x 我们build(a,b,x);

那么对于本题

if (a==b && c==d) { build(d,a,-x); build(b,c,x); }

if (a==b && c!=d) { build(d,a,-x-1); build(b,c,x-1); }

　　 if (a!=b) { build(d,a,-x-1); build(b,c,x-1); }

由于要保证图的连通性,记得加一个超级源点,向每个点加1条边

而且是车站,实际问题,每相邻2个站之间,至少需要1分钟.

顺便用了dfs版的spfa板子,跑得飞快

  1 #include<bits/stdc++.h>
  2 #define N 2005
  3 #define M 10005
  4 const long long inf=0x3f3f3f3f3f3f3f3f;
  5 typedef long long lld;
  6 using namespace std;
  7 struct rec
  8 {
  9     int go,next;
 10     long long v;
 11 }eg[M];
 12 int head[N],que[N],nn,k,a,b,c,p,n,du[N];
 13 lld dis[N];
 14 bool used[N];
 15 void read(int &a)
 16 {
 17     a=0;
 18     char c=getchar();
 19     while (c<=32) c=getchar();
 20     while (c>32) a=a*10+c-'0',c=getchar();
 21 }
 22 void build(int a,int b,long long c)
 23 {
 24     p++;
 25     eg[p].go=b;
 26     eg[p].next=head[a];
 27     eg[p].v=c;
 28     head[a]=p;
 29 }
 30 stack<int>S;
 31 int spfa()
 32 {
 33     for (int i=0;i<=n;i++)
 34     {
 35         S.push(i);
 36         du[i]=1;
 37         used[i]=1;
 38         dis[i]=0;
 39     }
 40     while (!S.empty())
 41     {
 42         int v=S.top();
 43         S.pop();
 44         used[v]=0;
 45         for (int u=head[v];u;u=eg[u].next )
 46         if (dis[eg[u].go]>dis[v]+eg[u].v)
 47         {
 48             dis[eg[u].go]=dis[v]+eg[u].v;
 49             if ((++du[eg[u].go])>nn)
 50             {
 51                 printf("IMPOSSIBLE");
 52                 return 0 ;
 53             }
 54             if (!used[eg[u].go]) S.push(eg[u].go ) ;
 55         }
 56     }
 57     return 1 ;
 58 }
 59 int T,x,d,tt;
 60 int main()
 61 {
 62     int tt=0;
 63     scanf("%d",&T);
 64     while (T--)
 65     {
 66         p=0;
 67         memset(que,0,sizeof(que));
 68         memset(used,0,sizeof(used));
 69         memset(du,0,sizeof(du));
 70         memset(head,0,sizeof(head));
 71         while (!S.empty()) S.pop();
 72         read(nn);read(k);read(x);
 73         for (int i=1;i<=k;i++)
 74         {
 75             read(a);read(b);read(c);read(d);
 76             if (a==b && c==d)
 77             {
 78                 build(d,a,-x);
 79                 build(b,c,x);
 80             }else
 81             if (a==b && c!=d)
 82             {
 83                 build(d,a,-x-1);
 84                 build(b,c,x-1);
 85             }else
 86             {
 87                 build(d,a,-x-1);
 88                 build(b,c,x-1);
 89             }
 90         }
 91         n=nn+1;
 92         for (int i=1;i<=nn;i++) build(n,i,0);
 93         for (int i=1;i<nn;i++) build(i+1,i,-1);
 94         tt++;
 95         printf("Case #%d: ",tt);
 96         int why=spfa();
 97         if (why) for (int i=2;i<=nn;i++) printf("%lld ",dis[i]-dis[i-1]);
 98         printf("
");
 99     }
100     return 0;
101 }