[SCOI2011]糖果
显然差分约束,根据条件建立所有边,注意相等建立双向边。
至于为什么跑最长路,我认为是只有式子 i - 0 >= 1才能建立0到 i (i从1到n)的边,这样才能把所有点连起来。
不过这里的题解没有建立0到 i 的所有边,因为从 0 开始直接spfa 判断 n 次 会TLE,就对每个点用dfs的spfa,这种处理对于负权环较快。ans开long long 。图不联通,对每个点spfa。
在spfa里面,每次访问过book标记,若可以变长 dis【v】< w,且正在进行 dfs ,就说明存在环。
只要不只对0spfa就不会TLE
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define ll long long
struct E{
int w,v,nxt;
};
int cnt,head[2000000],book[100005],dis[100005];
int tot[100005],in[100005];
E edge[300005];
int n,m;
void add(int u,int v,int w){
cnt++;
edge[cnt].v = v; edge[cnt].w = w;
edge[cnt].nxt = head[u]; head[u] = cnt;
}
bool spfa(int S){
book[S] = 1;
for(int v,w,i=head[S];i;i=edge[i].nxt){
v = edge[i].v; w = dis[S] +edge[i].w;
if(dis[v]<w){
tot[v]++;if(tot[v]>=n)return false;
if(book[v])return false;
dis[v]=w;
if(!spfa(v))return false;
}
}
book[S] = 0;
return true;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
int c,a,b;
scanf("%d %d %d",&c,&a,&b);
if(c==1){
add(a,b,0);
add(b,a,0);
in[b]++; in[a]++;
}else if(c==2){
add(a,b,1);
in[b]++;
}else if(c==3){
add(b,a,0);
in[a]++;
}else if(c==4){
add(b,a,1);
in[a]++;
}else{
add(a,b,0);
in[b]++;
}
if(c%2==0 && a==b) {
printf("-1\n");
return 0;
}
}
//for(int i=1;i<=n;i++) add(i,0,1);
for(int i=1;i<=n;i++)dis[i]=1;
int f=0;
for(int i=0;i<=n;i++){
if(!spfa(i)){
f = 1;break;
}
}
if(f)printf("-1\n");
else {
ll sum=0; for(int i=0;i<=n;i++)sum+=dis[i];
printf("%lld\n",sum);
}
return 0;
}