洛谷P3275 [SCOI2011]糖果(差分约束,最长路,Tarjan,拓扑排序)

时间:2021-12-11 13:41:42

洛谷题目传送门

差分约束模板题,等于双向连0边,小于等于单向连0边,小于单向连1边,我太蒻了,总喜欢正边权跑最长路。。。。。。

看遍了讨论版,我是真的不敢再入复杂度有点超级伪的SPFA的坑了

为了保证复杂度,需要缩点后用拓扑排序统计答案。首先全相等的点本质上是相同的,可以缩到一起,所以先来一波Tarjan把0环全缩起来。接着再考虑边权为1的边。如果这时候还出现了环(包括缩点以后的自环),一定是不存在方案的,这是可以用拓扑排序判断。否则,就是个DAG,拓扑排序也可以直接计算出答案。

统计答案要注意:因为缩了点,所以答案要乘上超级点的size;因为每个小朋友都要有糖,所以最后答案+n(或者也可以将虚点的d值初始化为1,只不过最后要减掉1)

我不会说我连Tarjan都不会写调了半个下午的

#include<cstdio>
#include<algorithm>
using namespace std;
#define I inline
#define R register
#define G ch=getchar()
#define REP for(i=1;i<=n;++i)
#define add(L,X,Y)\
l[++p]=L;to[p]=Y;\
ne[p]=he[X];he[X]=p;\
if(!tl[X])tl[X]=p//鬼畜tl指向链表尾部,方便链表合并
const int N=100009,M=N*3;
int p,df,tot,he[N],tl[N],ne[M],to[M],rd[N],d[N],low[N],dfn[N],sz[N],f[N],st[N];
bool l[M];
template<typename T>
I void in(R T&z){
R char G;
while(ch<'-')G;
z=ch&15;G;
while(ch>'-')z*=10,z+=ch&15,G;
}
void tarjan(R int x){
low[st[++p]=x]=dfn[x]=++df;
for(R int y,i=he[x];i;i=ne[i]){
if(l[i])continue;//只能缩0环
if(!dfn[y=to[i]]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(!f[y])low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
++tot;
do ++sz[f[st[p]]=x];
while(st[p--]!=x);
}
}
int main(){
R int p=0,n,k,S,o,x,y,i,j,cnt=0;
in(n);in(k);S=n+1;
R long long ans=n;//好像
while(k--){
in(o);in(x);in(y);
switch(o){
case 1:add(0,x,y);add(0,y,x);break;
case 2:add(1,x,y);break;
case 3:add(0,y,x);break;
case 4:add(1,y,x);break;
case 5:add(0,x,y);
}
}
for(i=1;i<=n;++i){add(0,S,i);}//虚点搞上
tarjan(S);
for(i=1;i<=S;++i){
x=f[i];
for(j=he[i];j;j=ne[j]){
y=to[j]=f[to[j]];//改一下
if(x!=y)++rd[y];//在新图上统计入度
else if(l[j]){puts("-1");return 0;}//自环可以直接判掉
}
}
for(i=1;i<=S;++i)//合并链表
if(i!=f[i])ne[tl[i]]=he[f[i]],he[f[i]]=he[i];
st[p=1]=S;
while(p){
++cnt;//统计进入拓扑排序的总点数
ans+=d[x=st[p--]]*sz[x];
for(i=he[x];i;i=ne[i]){
y=to[i];
d[y]=max(d[y],d[x]+l[i]);
if(!--rd[y])st[++p]=y;
}
}
printf("%lld\n",cnt<tot?-1:ans);
return 0;
}