/*
一道蛮简单的差分约束的感觉OTZ
然而有很多细节和技巧可以学习
首先我们要先了解一下差分约束然后再来做这题
我们可以考虑如果输入a,b,w w==1    那么a到b连一条权值1的边
w==-1 y到x连一条权值1的边
w==0  则两个点连一条权值0的无向边就好了
那么我们建立好了这个差分系统时
我们就可以跑一边最长路了
因为是最长路所以d[]初始化要是负无穷大
和最短路一样但是是对立的
如果有一个正权环    那么我们肯定可以沿着这条正权环绕啊绕得到更长的最长路
所以不存在正确的k时就是不存在最长路的情况
即比如a到b权1(a比b大)  b到c权1(b比c大)
而c到a也权1(c比a大)   自然是无解的
所以我们就跑SPFA最长路+判负环就好了
然后就是我们可以看到
SPFA是求单源最短路径
而这道题并没有明确的起点终点
所以要得到每个点的d[]取最大值了
那么我们怎么做到呢？
这里有一个小技巧了
我们设置一个虚的源点0
然后再从0到每个顶点连一条权值为0的有向边
这样就可以求出这个所有的d[]的最大值了
OTZ被坑了很久一直过不了自己的数据包
想了半天
长见识了
然后一开始写的是STL队列   后来换成了手写循环队列练习一下Orz
窝好弱啊
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1050;
const int MAXV=20005;
const int INF=0x7ffffff;
struct Edge
{
    int to,w,next;
    Edge()
    {
        to=next=w=-1;
    }
}e[MAXV];
int first[MAXN];
int cnt[MAXN];
int d[MAXN];
int q[MAXN];
bool in[MAXN];
int front,rear;
int n,m;
int tot;
int ans;

void inline Add_Edge(int x,int y,int w)
{
    tot++;
    e[tot].to=y;
    e[tot].w=w;
    e[tot].next=first[x];
    first[x]=tot;
}

void init()
{
    memset(first,-1,sizeof(first));
    int x,y,w;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>w;
        if(w==1)
            Add_Edge(x,y,1);
        else    if(w==-1)
            Add_Edge(y,x,1);
        else    if(w==0)
            Add_Edge(x,y,0),
            Add_Edge(y,x,0);
    }
    for(int i=1;i<=n;i++)//设一个虚源点0作为SPFA起点
        Add_Edge(0,i,0);
}

void SPFA(int s)
{
    for(int i=1;i<=n;i++)
        d[i]=-INF;
    d[s]=0;
    q[rear++]=s;
    in[s]=1;
    cnt[s]++;
    while(front!=rear)
    {
        int x=q[front];
        front=(front+1)%1005;   
        in[x]=0;
        for(int i=first[x];i!=-1;i=e[i].next)
        {
            int u=e[i].to;  int w=e[i].w;
            if(d[u]<d[x]+w)//最长路
            {
                d[u]=d[x]+w;
                if(!in[u])
                {
                    q[rear]=u;
                    rear=(rear+1)%1005;
                    in[u]=1;
                    if(++cnt[u]>n)
                    {
                        cout<<"NO"<<endl;
                        exit(0);
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,d[i]);
    cout<<ans<<endl;
}

int main()
{
    init();
    SPFA(0);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    const ll oo_min=0xcfcfcfcfcfcfcfcf,oo_max=0x3f3f3f3f3f3f3f3f;
    
    ll n,m;
    vector<ll> a,b,c,vis,cnt,dist;
    vector<vector<ll>> e,l;
    deque<ll> q;
    
    void bfs_resize(ll size)
    {
        vis.resize(size,0),cnt.resize(size,0);
        dist.resize(size,oo_min);
        e.resize(size),l.resize(size);
        for (ll i=0;i<size;i++)
            e[i].clear(),l[i].clear();
        q.clear();
    }
    void add_edge(ll x,ll y,ll d)
    {
        e[x].push_back(y);
        l[x].push_back(d);
    }
    ll bfs()
    {
        dist[0]=0;
        for (vis[0]=1,cnt[0]++,q.push_back(0);!q.empty();vis[q.front()]=0,q.pop_front())
        {
            ll now=q.front();
            for (ll i=0;i<e[now].size();i++)
                if (dist[now]+l[now][i]>dist[e[now][i]])
                {
                    dist[e[now][i]]=dist[now]+l[now][i];
                    if (vis[e[now][i]]==0)
                    {
                        if (cnt[e[now][i]]>=n)
                            return -1;
                        else
                        {
                            vis[e[now][i]]=1,cnt[e[now][i]]++;
                            q.push_back(e[now][i]);
                        }
                    }
                    else if (now==e[now][i])
                        return -1;
                }
        }
        ll ans=-1;
        for (ll i=1;i<=n;i++)
            ans=max(ans,dist[i]);
        return ans;
    }
    void main()
    {
        scanf("%lld%lld",&n,&m);
        a.resize(m,0),b.resize(m,0),c.resize(m,0);
        for (ll i=0;i<m;i++)
            scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
        bfs_resize(n+1);
        for (ll i=1;i<=n;i++)
            add_edge(0,i,0);
        for (ll i=0;i<m;i++)
            if (c[i]==-1)
                add_edge(a[i],b[i],1);
            else if (c[i]==1)
                add_edge(b[i],a[i],1);
            else if (c[i]==0)
                add_edge(a[i],b[i],0),add_edge(b[i],a[i],0);
        ll ans=bfs();
        if (ans==-1)
            printf("NO\n");
        else
            printf("%lld\n",ans);
    }
}

int main()
{
    dts::main();
}

缩点+差分
首先将所有等号边连接的连通块缩点,大于号边反向连(这样就全是小于号了)
然后将缩点后的图进行差分找最长路即可
缩点用并查集,差分用拓扑,这个就不解释了吧

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define N 1001
#define next nextt
using namespace std;
int n,m,fa[N],val[N],deg[N],s[N*100],t[N*100],tot=0;
int ce[N],to[N*200],next[N*200],cnt=0,ans=0;
int find(int v){//并查集缩点 
    return fa[v]==v?v:fa[v]=find(fa[v]);
}
void turbo(){//拓扑差分 
    int i,qu[N*2],l=1,len=0,p,v;
    for(i=1;i<=n;i++){
        if(deg[i]==0){
            val[i]=0;
            qu[++len]=i;
        }
    }
    while(l<=len){
        v=qu[l];
        l++;
        for(p=ce[v];p;p=next[p]){
            deg[to[p]]--;
            if(deg[to[p]]==0){
                qu[++len]=to[p];
                val[to[p]]=val[v]+1;
                ans=max(ans,val[to[p]]);
            }
        }
    }
}
int main(){
    int i,a,b,k;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        fa[i]=i;
        deg[i]=ce[i]=0;
    }
    for(i=1;i<=m;i++){
        cin>>a>>b>>k;
        if(k==-1){
            s[++tot]=a;
            t[tot]=b;
        }
        if(k==1){
            s[++tot]=b;
            t[tot]=a;
        }
        if(k==0){
            a=find(a);
            b=find(b);
            if(a!=b) fa[a]=b;
        }
    }
    for(i=1;i<=tot;i++){
        a=find(s[i]);
        b=find(t[i]);
        to[++cnt]=b;
        deg[b]++;
        next[cnt]=ce[a];
        ce[a]=cnt;
    }
    turbo();
    for(i=1;i<=n;i++){
        if(deg[i]){
            cout<<"NO";
            return 0;
        }
    }
    cout<<ans;
    return 0;
}

为什么都提差分约束啊？
直接缩点，然后按照出度的大小bfs就可以了。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

int n,m;
int fa[1001];
vector<int> g[1001],g2[1001],re[1001];
bool a[1001][1001];
int bel[1001];
int out[1001];
int cnt;
int ans;
int tot;
struct node {
    int id,v;
};
queue<node> q;
int find(int x) {
    return (x==fa[x])?x:(fa[x]=find(fa[x]));
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,n) fa[i]=i;
    FOR(i,m) {
        int x,y,z;
        cin>>x>>y>>z;
        if (z==0) {
            int u=find(x),v=find(y);
            if (u!=v) fa[u]=v;
        } else if (z==1) {
            g2[x].pb(y);
        } else {
            g2[y].pb(x);
        }
    }
    FOR(i,n) {
        if (bel[find(i)]==0) {
            bel[find(i)]=++cnt;
        }
    }
    //FOR(i,n) cout<<bel[i]<<endl;
    FOR(i,n) {
        int t=bel[find(i)];
        for (int j=0;j<g2[i].size();j++) {
            int x=g2[i][j];
            int t2=bel[find(x)];
            if (t==t2) {
                cout<<"NO"<<endl;
                return 0;
            }
            if (!a[t][t2]) {
                a[t][t2]=1;
                g[t].pb(t2);
                re[t2].pb(t);
                ++out[t];
            }
        }
    }
    /*
    cout<<cnt<<endl;
    FOR(i,cnt) {
        for (int j=0;j<g[i].size();j++) cout<<g[i][j]<<" ";
        cout<<endl;
    }*/
    FOR(i,cnt) if (!out[i]) {
        ++tot;
        q.push(node{i,0});
    }
    while (q.size()) {
        node x=q.front();q.pop();
        for (int i=0;i<re[x.id].size();i++) {
            int to=re[x.id][i];
            if (--out[to]==0) {
                q.push(node{to,x.v+1});
                ++tot;
                ans=max(ans,x.v+1);
            }
        }
    }
    if (tot!=cnt) {
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<ans<<endl;
    return 0;
}

P1094关系运算图
Accepted

记录信息

评测状态 Accepted
题目 P1094 关系运算图
递交时间 2015-07-10 23:07:45
代码语言 C++
评测机 VijosEx
消耗时间 31 ms
消耗内存 776 KiB
评测时间 2015-07-10 23:07:47

评测结果

编译成功

foo.cpp: In function 'void spfa()':
foo.cpp:42:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( i = 0 ; i < link[ now ].size() ; i++ )
^

测试数据 #0: Accepted, time = 0 ms, mem = 612 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 604 KiB, score = 20

测试数据 #2: Accepted, time = 31 ms, mem = 776 KiB, score = 20

测试数据 #3: Accepted, time = 0 ms, mem = 624 KiB, score = 20

测试数据 #4: Accepted, time = 0 ms, mem = 596 KiB, score = 20

Accepted, time = 31 ms, mem = 776 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

int n , m;
vector < int > link[10000 + 2];
vector < int > value[10000 + 2];
int x , y , vt;
int dist[10000 + 2];
bool use[10000 + 2];
int i;
queue < int > q;
bool flag;
int ans;

int max( int a , int b )
{
if( a > b )
return a;
return b;
}

void spfa()
{
int i , now , cur , w;
q.push( 0 );
dist[0] = 0;
while( !q.empty() )
{
now = q.front();
q.pop();
use[ now ] = 0;
if( dist[now] > n )
{
flag = 1;
break;
}
for( i = 0 ; i < link[ now ].size() ; i++ )
{
cur = link[ now ][i];
w = value[ now ][i];
if( dist[ cur ] < dist[ now ] + w )
{
dist[ cur ] = dist[ now ] + w;
if( !use[ cur ] )
{
use[ cur ] = 1;
q.push( cur );
}
}
}
}
return;
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 0 ; i < m ; i++ )
{
scanf( "%d %d %d" , &x , &y , &vt );
if( vt == -1 )
{
link[x].push_back( y );
value[x].push_back( 1 );
}
else if( vt == 1 )
{
link[y].push_back( x );
value[y].push_back( 1 );
}
else
{
link[x].push_back( y );
link[y].push_back( x );
value[x].push_back( 0 );
value[y].push_back( 0 );
}
}
for( i = 1 ; i <= n ; i++ )
{
link[0].push_back( i );
value[0].push_back( 0 );
}
memset( dist , -1 , sizeof( dist ) );
spfa();
for( i = 1 ; i <= n ; i++ )
ans = max( ans , dist[i] );
if( flag )
cout << "NO" << endl;
else
cout << ans << endl;
//system( "pause" );
return 0;
}
真~差分约束！

1

转载一篇很好的差分约束教程：
http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#include <tuple>

using namespace std;

const int maxN = 1000 + 5;
const int maxM = 10000 + 5;
const int inf = 0x3f3f3f3f;

//first: to
//second: len
vector<pair<int, int>> elist[maxN];
//int inDeg[maxN] = {0};
bool inStack[maxN] = {false};
int dist[maxN];
int N, M;

void input()
{
    auto addEdge = [] (int f, int t, int d) -> void {
        elist[f].emplace_back(t, d);
        //inDeg[t] += 1;
    };

    scanf("%d%d", &N, &M);
    for (int u, v, f, i = 0; i < M; i++)
    {
        scanf("%d%d%d", &u, &v, &f);
        switch (f)
        {
        case -1:
            addEdge(v, u, -1);
            break;
        case 0:
            addEdge(u, v, 0);
            addEdge(v, u, 0);
            break;
        case 1:
            addEdge(u, v, -1);
            break;
        default:
            break;
        }
    }

    for (int i = 1; i <= N; i++)
        addEdge(0, i, 0);
}

void initDfs()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
}

bool dfs(int cur)
{
    inStack[cur] = true;

    int to, len;
    for (auto& pr: elist[cur])
    {
        tie(to, len) = pr;
        if (dist[cur] + len >= dist[to])
            continue;
        dist[to] = dist[cur] + len;
        if (inStack[to] || !dfs(to))
            return false;
    }

    inStack[cur] = false;
    return true;
}

void solve()
{
    initDfs();
    if (!dfs(0))
    {
        printf("NO");
        return;
    }
    printf("%d", -*min_element(dist + 1, dist + N + 1));
}

int main()
{
    input();
    solve();
    return 0;
}

裸差分约束系统。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

/*
输入格式

共二行，第一行有二个空格隔开的整数n和m。
n表示G的结点个数，m表示G的边数，其中1<=n<=1000, 0<=m<=10000。
全部结点用1到n标出，图中任何二点之间最多只有一条边，且不存在自环。
第二行共有3m个用空格隔开的整数，第3i-2和第3i-1（1<=i<=m）个数表示第i条边的顶点。
第3i个数表示第i条边上的符号，其值用集合{-1，0，1}中的数表示：-1表示‘<’, 0 表示‘=’, 1表示‘>’。

*/

int n,m,d[2000],ans=0x3f3f3f3f;

struct e{int from,to,cost;};

vector<e>G;

void BF(){
int update=true,tot=0;
while(update){
update=false;
tot++;
if(tot>n)break;
for(int i=0;i<G.size();i++){
int from=G[i].from;
int to=G[i].to;
int cost=G[i].cost;
if(d[to]>d[from]+cost)
d[to]=d[from]+cost,update=true;
}
}
if(tot>n)return puts("NO"),void();
for(int i=1;i<=n;i++)ans=min(ans,d[i]);
printf("%d\n",abs(ans));
}

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z==-1){
//x<y --> x-y<=-1
G.push_back((e){y,x,-1});
}else if(z==0){
//x-y<=0
//y-x<=0
G.push_back((e){x,y,0});
G.push_back((e){y,x,0});
}else{
//x>y --> y-x>=-1
G.push_back((e){x,y,-1});
}
}
BF();
}

var h,t,i,j,k,m,n,p,ans:longint;
b,c,d,w:array[0..10000] of longint;
x,y,z:longint;
a:array[0..1000,0..1000] of longint;
v:array[0..10000] of boolean;
procedure spfa(x:Longint);
var k:longint;
begin
fillchar(v,sizeof(v),false);
fillchar(d,sizeof(d),0);
fillchar(w,sizeof(w),0);
h:=0;
t:=0;
inc(t);
w[t]:=x;
v[x]:=true;
d[x]:=0;
while (h<>t) do
begin
h:=h mod n +1;
k:=w[h];
inc(c[k]);
if c[k]>2*n then begin writeln('NO'); halt; end;
v[k]:=false;
for i:=1 to n do
if (d[k]+a[k,i]<d[i]) and (a[k,i]<>0) then
begin
d[i]:=d[k]+a[k,i];
if not v[i] then
begin
t:=t mod n +1;
w[t]:=i;
v[i]:=true;
end;
end;
end;
end;
begin
read(m,n);
for i:=1 to m do
begin
read(x,y,z);
if z=1 then begin
a[y,x]:=-1;
// a[y,x]:=1;
end;
if z=-1 then begin
a[x,y]:=-1;
// a[x,y]:=1;
end;
end;
inc(n);
for i:=1 to n-1 do
begin
a[n,i]:=-1;
//a[i,n]:=1;
a[i,i]:=10000000;
end;
spfa(n);
ans:=100000;
for i:=1 to n-1 do
if d[i]<ans then ans:=d[i];
writeln(abs(ans)-1);
end.

为什么运行错误~？？？？？

#include<cstdio>
const int maxn=2005,maxm=20005;
int m,n;
int map[maxm][3]={0},cost[maxn]={0};
bool updated=true;
int times=0;
int main(){
scanf("%d %d\n",&n,&m);
for(int i=0;i<m;i++){
int x,y,z;
scanf("%d %d %d ",&x,&y,&z);
if(z==1){
map[i][0]=x;
map[i][1]=y;
map[i][2]=z;
}else if(z==0){
map[i][0]=x;
map[i][1]=y;
map[i][2]=z;
i++;m++;
map[i][1]=x;
map[i][0]=y;
map[i][2]=z;
}else{
map[i][0]=y;
map[i][1]=x;
map[i][2]=1;
}
}
while(updated&&times<=n){
updated=false;
times++;
for(int i=0;i<m;i++){
int preput=cost[map[i][0]]+map[i][2];
if(cost[map[i][1]]<preput){
cost[map[i][1]]=preput;
updated=true;
}else;
}
}
if(times<=n){
int ans=0;
for(int i=1;i<=n;i++){
if(ans<cost[i])ans=cost[i];
else;
}
printf("%d\n",ans);
}else printf("NO\n");
}
权为0的边必须双向，否则第2,3点过不去。

经典啊~~~~~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

费了快两个小时了... 终于~~

晒程序：

var

a,e:array [0..1000,0..1000] of longint;

b,d:array [0..1000] of longint;

f:array [1..10000,1..2] of longint;

c:array [1..1000] of boolean;

ans,num,i,j,k,l,n,m,x,y:longint;

stop:boolean;

procedure bll(k,o:longint);

var

j,q,p:longint;

begin

c[k]:=false;

if k=f then begin writeln('NO');stop:=true;exit;end;

if a[k,0]=0 then exit;

for j:=1 to a[k,0] do

if c[a[k,j]] then

begin

bll(a[k,j],o);

if stop then exit;

end;

end;

procedure bl(k:longint);

var

i,j,l,q,p:longint;

begin

c[k]:=false;

for i:=1 to a[k,0] do

if c[a[k,i]] then begin

bl(a[k,i]);

if b[k]

搞笑 这道题居然有环.用spfa判断环 只要记录每个点的入队列次数 如果次数大于点的总数就有环.

也是道蛮经典的题目。

其实很简单。构造一个图。

如果an then begin writeln('NO');halt end;

if v[i]=0 then

begin

inc(ed);

c[ed]:=i;

v[i]:=1

end;

end;

inc(st);

end;

for i:=1 to n do if dis[i]>max then max:=dis[i];

end;

begin

init;

spfa;

writeln(max-1);

end.

var

i,j,x,y,z,n,m,k,max:longint;

count,a,into:array[1..1000] of longint;

b:array[1..1000] of boolean;

g,map:array[1..1000,1..1000] of integer;

begin

read(n,m);

fillchar(g,sizeof(g),0);

for i:=1 to m do

begin

read(x,y,z);

if z=-1 then g[x,y]:=1;

if z=1 then g[y,x]:=1;

if z=0 then a[x]:=y;

end;

fillchar(b,sizeof(b),true);

for k:=1 to n do

if a[k]0 then for i:=1 to n do

begin

if (g=1)and(ia[k]) then g[i,a[k]]:=1;

if (g[k,i]=1)and(ia[k]) then g[a[k],i]:=1;

b[k]:=false;

end;

fillchar(map,sizeof(map),0);

for i:=1 to n do

for j:=1 to n do

if (b[i])and(b[j]) then begin

map:=g;

if map=1 then inc(into[j]);

end;

fillchar(count,sizeof(count),0);

for i:=1 to n do

begin

j:=1;

while (j

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

在老师强烈建议用并查集+拓扑排序的情况下我终于用SPFA秒之。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

传说中的bellman_ford

toplogical sort

终于明白这道题目的的AC率为什么会那么低了...

首先要用邻接表

接着bellman_ford

注意，等于的时候要连接一条双向的权为0的边（否则只能60分）

差分约束

以前用spfa写，不知怎么始终错，今天突发奇想，去学了bellman_ford然后就对了....

倒...看牛人们说的是求最长路，但是我不知怎么写了个最短路...竟然AC?!

看样子RP+++

---|---|---|---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 244ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：244ms

必须从源向所有点连边，我沙茶了！