Go语言视频零基础入门到精通

admin

洛谷题目传送门
差分约束模板题，等于双向连0边，小于等于单向连0边，小于单向连1边，我太蒻了，总喜欢正边权跑最长路。。。。。。
看遍了讨论版，我是真的不敢再入复杂度有点超级伪的SPFA的坑了
为了保证复杂度，需要缩点后用拓扑排序统计答案。首先全相等的点本质上是相同的，可以缩到一起，所以先来一波Tarjan把0环全缩起来。接着再考虑边权为1的边。如果这时候还出现了环（包括缩点以后的自环），一定是不存在方案的，这是可以用拓扑排序判断。否则，就是个DAG，拓扑排序也可以直接计算出答案。
统计答案要注意：因为缩了点，所以答案要乘上超级点的size；因为每个小朋友都要有糖，所以最后答案+n（或者也可以将虚点的d值初始化为1，只不过最后要减掉1）
我不会说我连Tarjan都不会写调了半个下午的

1. [code]#include<cstdio>
2. #include<algorithm>
3. using namespace std;
4. #define I inline
5. #define R register
6. #define G ch=getchar()
7. #define REP for(i=1;i<=n;++i)
8. #define add(L,X,Y)\
9. l[++p]=L;to[p]=Y;\
10. ne[p]=he[X];he[X]=p;\
11. if(!tl[X])tl[X]=p//鬼畜tl指向链表尾部，方便链表合并
12. const int N=100009,M=N*3;
13. 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];
14. bool l[M];
15. template<typename T>
16. I void in(R T&z){
17.     R char G;
18.     while(ch<"-")G;
19.     z=ch&15;G;
20.     while(ch>"-")z*=10,z+=ch&15,G;
21. }
22. void tarjan(R int x){
23.     low[st[++p]=x]=dfn[x]=++df;
24.     for(R int y,i=he[x];i;i=ne[i]){
25.         if(l[i])continue;//只能缩0环
26.         if(!dfn[y=to[i]]){
27.             tarjan(y);
28.             low[x]=min(low[x],low[y]);
29.         }
30.         else if(!f[y])low[x]=min(low[x],dfn[y]);
31.     }
32.     if(low[x]==dfn[x]){
33.         ++tot;
34.         do ++sz[f[st[p]]=x];
35.         while(st[p--]!=x);
36.     }
37. }
38. int main(){
39.     R int p=0,n,k,S,o,x,y,i,j,cnt=0;
40.     in(n);in(k);S=n+1;
41.     R long long ans=n;//好像
42.     while(k--){
43.         in(o);in(x);in(y);
44.         switch(o){
45.             case 1:add(0,x,y);add(0,y,x);break;
46.             case 2:add(1,x,y);break;
47.             case 3:add(0,y,x);break;
48.             case 4:add(1,y,x);break;
49.             case 5:add(0,x,y);
50.         }
51.     }
52.     for(i=1;i<=n;++i){add(0,S,i);}//虚点搞上
53.     tarjan(S);
54.     for(i=1;i<=S;++i){
55.         x=f[i];
56.         for(j=he[i];j;j=ne[j]){
57.             y=to[j]=f[to[j]];//改一下
58.             if(x!=y)++rd[y];//在新图上统计入度
59.             else if(l[j]){puts("-1");return 0;}//自环可以直接判掉
60.         }
61.     }
62.     for(i=1;i<=S;++i)//合并链表
63.         if(i!=f[i])ne[tl[i]]=he[f[i]],he[f[i]]=he[i];
64.     st[p=1]=S;
65.     while(p){
66.         ++cnt;//统计进入拓扑排序的总点数
67.         ans+=d[x=st[p--]]*sz[x];
68.         for(i=he[x];i;i=ne[i]){
69.             y=to[i];
70.             d[y]=max(d[y],d[x]+l[i]);
71.             if(!--rd[y])st[++p]=y;
72.         }
73.     }
74.     printf("%lld\n",cnt<tot?-1:ans);
75.     return 0;
76. }

复制代码

[/code]