[文章目录]
Description
幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
差分约数模板题。
讲题目转换成单源最长路来解。如果A>B说明A到源点的距离时刻大于B，又期望和最小，那么由B向A连一条边权为1的边，其余条件同理。再有源点向所有点连边。如果有正权环那么无解。
然后就变成了单源最短路的问题了。spfa求最长路判正权环。然后就tm发现数据完全是对着代码卡的啊。源点向所有点连边的顺序决定了你的时间。
由于边权为1或0，想到了一个tarjan+topsort的办法，如果强联通分量里连有正权边那么无解，然后就变成了个拓扑图，拓扑直接就可以求出来单源最长路。
好像不会被卡？然后早上写出来，1A.感觉还是可行的。
时间复杂度感觉妙啊。
附上代码：
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
typedef long long ll;
int n,k;
ll fna;
int head[N],to[N<<1],nxt[N<<1],f[N<<1],cnt;
int read()
{
char ch=getchar(); int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
}
int bel[N],dfn[N],low[N],z[N],top,tot,ans,num[N];
bool inz[N];
void tarjan(int x)
{
dfn[x]=low[x]=++tot; z[++top]=x; inz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
else if(inz[to[i]]) low[x]=min(low[x],dfn[to[i]]);
}
if(low[x]==dfn[x])
{
ans++; int t;
do
{
t=z[top--];
inz[t]=0;
bel[t]=ans;
num[ans]++;
}while(t!=x);
}
}
int head1[N],to1[N<<1],nxt1[N<<1],cnt1,rd[N],f1[N],dis[N];
void add1(int x,int y,int z)
{
to1[++cnt1]=y;
nxt1[cnt1]=head1[x];
head1[x]=cnt1;
f1[cnt1]=z;
rd[y]++;
}
bool check()
{
int i,j;
for(i=1;i<=n;++i)
{
for(j=head[i];j;j=nxt[j])
{
if(bel[to[j]]!=bel[i]) add1(bel[i],bel[to[j]],f[j]);
else if(f[j]) return true;
}
}
return false;
}
queue<int>q;
void topsort()
{
int x,i;
while(!q.empty()) q.pop();
for(i=1;i<=ans;++i)
if(rd[i]==0) dis[i]=1,q.push(i);
while(!q.empty())
{
x=q.front(); q.pop();
for(i=head1[x];i;i=nxt1[i])
{
rd[to1[i]]--;
dis[to1[i]]=max(dis[to1[i]],dis[x]+f1[i]);
if(!rd[to1[i]]) q.push(to1[i]);
}
}
}
int main()
{
scanf("%d%d",&n,&k);
int i,x,y,z;
while(k--)
{
z=read(); x=read();y=read();
if(x!=y)
{
switch(z)
{
case 1:add(x,y,0); add(y,x,0); break;
case 2:add(x,y,1); break;
case 3:add(y,x,0); break;
case 4:add(y,x,1); break;
case 5:add(x,y,0); break;
}
}
else if(z==2||z==4) {puts("-1"); return 0;}
}
for(i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
if(check()) {puts("-1"); return 0;}
topsort();
for(i=1;i<=ans;++i) fna+=1ll*dis[i]*num[i];
printf("%lld",fna);
return 0;
}