[CH Round #23] 小 K 的农场

2014-07-07
竞赛题解 / 图论
ContestHunter差分约束最短路

描述 Description

小 K 在 MC 里面建立很多很多的农场，总共 n 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 m 个），以下列三种形式描述：农场 a 比农场 b 至少多种植了 c 个单位的作物，农场 a 比农场 b 至多多种植了 c 个单位的作物，农场 a 与农场 b 种植的作物数一样多。但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式 InputFormat

第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息的数目。

接下来 m 行：

如果每行的第一个数是 1，接下来有三个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物。

如果每行第一个数是 2，接下来有三个整数 a，b，c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物。

如果每行第一个数是 3，接下来有两个整数 a,b，表示农场 a 种植的数量与 b 一样多。

输出格式 OutputFormat

如果存在某种情况与小 K 的记忆吻合，输出”Yes”，否则输出”No”。

样例输入 SampleInput

3 3
3 1 2
1 1 3 1
2 2 3 2

样例输出 SampleOutput

Yes

数据范围和注释 Hint

对于 10% 的数据，1 <= n ,m<= 10.

对于 100% 的数据，1 <= n,m,a,b,c <= 10000.

来源 Source

Kpmcup#0

CH Round #23

代码 Code

差分约束系统. 对于约束 1, 连边 (a,b,-c); 约束 2. 连边(b,a,c); 约束 3, 连边(a,b,0),(b,a,0)。建一个起点 s，向所有点连一条(s,i,0) 的边。进行 dfs 版 spfa，图中存在负权环即是无解。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/27.11;
struct edge
{
    int to,next,s;
}e[30005];
int head[10005];
bool used[10005];
int dis[10005];
int i,j,t,n,m,l,r,k,z,y,x,p;
inline void ins(int x,int y,int z)
{
    e[++p].to=y;e[p].next=head[x];e[p].s=z;head[x]=p;
}
bool spfa(int x)
{
    int i,j,t;
    bool b;
    used[x]=true;
    for (i=head[x];i;i=e[i].next)
    {
        if (dis[x]+e[i].s<dis[e[i].to])
        {
            dis[e[i].to]=dis[x]+e[i].s;
            if (used[e[i].to]) return false;
            else b=spfa(e[i].to);
        }
    }
    used[x]=false;
    return true;
}
int main()
{
    memset(used,false,sizeof(used));
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) dis[i]=inf;
    p=0;
    for (i=1;i<=n;i++) ins(0,i,0);
    for (i=1;i<=m;i++)
    {
        scanf("%d",&t);
        if (t==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            ins(x,y,-z);
        }
        if (t==2)
        {
            scanf("%d%d%d",&x,&y,&z);
            ins(y,x,z);
        }
        if (t==3)
        {
            scanf("%d%d",&x,&y);
            ins(x,y,0);
            ins(y,x,0);
        }
    }
    if (spfa(0)==false) printf("No\n");
    else printf("Yes\n");
    return 0;
}