2018-5-21 ~ 2018-5-30集训感想
首先 感谢 xiaoyao24256大佬 给我的blog（虽然只用一天QWQ）
这几天来到了浙江集训 爽爆（假的qwq）
尽管这几天学到了好多知识 但我还是个蒟蒻555
从5.29的ACM赛先说吧
比赛名称叫ACM欢乐赛，做题不欢乐，但是吃KFC吃的很欢乐嘿嘿嘿
一开始的时候 我们小组比其他小组早A了前2道题（虽然不是最早）
然后然后然后我就很开心
于是我们就卡在了第三题……
我们组一个大佬想出来了一个gcd的算法（我不会告诉你他就是给我号的人）
结果不知道什么玄学原因 我们组否认了这个算法 去刚第四题
为什么要否认呢？我也不知道啊……鬼知道那就是正解qwq
附上核心代码
1 read(p) , read(q) , read(b); 2 3 register ll Gcd = gcd(p,q); 4 q /= Gcd; 5 Gcd = b; 6 7 for(; q!=-1; ) { 8 Gcd = gcd(q,Gcd); 9 q /= Gcd; 10 if(Gcd == 1) break; 11 } 12 13 if(q == 1) puts("Finite"); 14 else puts("Infinite");
第四题……不想说什么了
我推了快1个小时的数学解
然后推出来了一个玄学的东西：
if len%4 == 1 输出头尾各一个数
if len%4 == 2 输出头尾各2个数
if len%4 == 3 输出第一个数、第三个数、倒一、倒三这些数
if len%4 == 0 输出所有数
正当我推得非常开心的时候 验证了下len=12的情况
然后就发现这个做法是错误的
于是 MMP ……
比赛结束之后我才发现这道是一道非常！水的！区间DP
哇哇哇气死了
依然附上代码
1 for(register int i=n-1; i>=1; i--) { 2 for(register int j=i+1; j<=n; j++) { 3 f[i][j] = f[i][j-1] ^ f[i+1][j]; 4 g[i][j] = maxest(f[i][j],g[i][j-1],g[i+1][j]); 5 } 6 }
我们最后选择直接去看第7题（垃圾AtCoder）
想出了两个类似正解的方法
嗯其实不是正解 最后测了WA的不要不要的
逃）
嗯那两个算法就是打表和随机数
事实证明打表能过更多的点
诶呀打表是我想出来的~
我觉得我可以把表交上来
嗯算了太大了不交了qwq
我不会告诉你我其实在凑字数
好了好了我们来讲一下正事吧
线段树
对这就是一个很神奇的东西
我们先来引入一个题目：戳我
假如说这道题目没有修改这这个操作，我们用前缀和维护一下就行了
加了修改之后，我们能想到的最朴素的做法是什么呢？
当然就是枚举 L - R 之间每个数然后加上x
求和也是一项一项加起来，这样复杂的是O（N^2）的
一看数据，喊出GG~
那我们有没有什么奇技淫巧降低复杂度呢？
线段树就是为了这个而生的。
就让我来简介一下线段树吧：
线段树是一个二叉树，每个子节点里存放一段区间的左右边界还有子节点的信息，可以是一段区间的和、最大值、最小值等等等等
为了更好的理解线段树，我厚颜无耻的拿了网上某个大佬的图来解释
算了中间一堆可以介绍的现在也写不了了，就不介绍了，有没感觉自己期待了半天却……嗯哼~
我直接贴代码了欸嘿
1 // luogu-judger-enable-o2 2 #include <iostream> 3 #include <cstdio> 4 5 using namespace std; 6 7 typedef long long ll; 8 const int Maxn = 400010; 9 int n , m; 10 int a[Maxn]; 11 struct SegmentTree { 12 ll sum; /* 1的总数 */ 13 ll tag; /* 标记 */ 14 int leftbound; 15 int rightbound; 16 } Tree[Maxn]; 17 18 inline void Build(int root, int left , int right) { 19 20 Tree[root].leftbound = left; 21 Tree[root].rightbound = right; 22 if(left == right) Tree[root].sum = a[left]; 23 else { 24 register int Mid = ( left + right ) / 2; 25 Build(root*2,left,Mid); 26 Build(root*2+1,Mid+1,right); 27 Tree[root].sum = Tree[root*2].sum + Tree[root*2+1].sum; 28 } 29 30 } 31 32 inline void Downtag(int root) { 33 34 if(Tree[root].tag) { 35 Tree[root*2].tag += Tree[root].tag; 36 Tree[root*2+1].tag += Tree[root].tag; 37 Tree[root*2].sum += ( Tree[root*2].rightbound - Tree[root*2].leftbound + 1 ) * Tree[root].tag; 38 Tree[root*2+1].sum += ( Tree[root*2+1].rightbound - Tree[root*2+1].leftbound + 1 ) * Tree[root].tag; 39 Tree[root].tag = 0; 40 } 41 42 } 43 44 inline void Modify(int root , int left , int right , int delta) { 45 46 if(Tree[root].leftbound >= left && Tree[root].rightbound <= right) { 47 Tree[root].tag += delta; 48 Tree[root].sum += ( Tree[root].rightbound - Tree[root].leftbound + 1 ) * delta; 49 } else { 50 Downtag(root); 51 register int Mid = ( Tree[root].leftbound + Tree[root].rightbound ) / 2; 52 if(left <= Mid) Modify(root*2,left,right,delta); 53 if(right > Mid) Modify(root*2+1,left,right,delta); 54 Tree[root].sum = Tree[root*2].sum + Tree[root*2+1].sum; 55 } 56 57 } 58 59 inline ll Query(int root , int left , int right) { 60 61 if(Tree[root].leftbound >= left && Tree[root].rightbound <= right) { 62 return Tree[root].sum; 63 } else { 64 Downtag(root); 65 register ll ans = 0; 66 register int Mid = ( Tree[root].leftbound + Tree[root].rightbound ) / 2; 67 if(left <= Mid) ans += Query(root*2,left,right); 68 if(right > Mid) ans += Query(root*2+1,left,right); 69 return ans; 70 } 71 72 } 73 74 int main() { 75 76 scanf("%d%d",&n,&m); 77 78 for(register int i=1; i<=n; i++) 79 scanf("%d",&a[i]); 80 81 Build(1,1,n); 82 83 for(register int i=1,x,y,z,k; i<=m; i++) { 84 scanf("%d%d%d",&z,&x,&y); 85 if(z == 1) { 86 scanf("%d",&k); 87 Modify(1,x,y,k); 88 } else printf("%lld ",Query(1,x,y)); 89 } 90 91 return 0; 92 93 }
额开头那个氧气优化别在意哈~
树状数组
这个东西嘛
跟线段树很像的
就是用一个lowbit瞎**搞
然后利用logn的时间求出来
这里放一个题目：戳我
代码如下qwq
1 #include <bits/stdc++.h> 2 3 using namespace std ; 4 5 const int MAXN = 500010; 6 int n,m; 7 int a[MAXN]; 8 int c[MAXN]; 9 10 inline void read(int &x) { 11 int num = 0 , negative = 0; 12 char ch = getchar(); 13 14 while((ch < '0' || ch > '9') && ch != '-') 15 ch = getchar(); 16 17 if(ch == '-') negative = 1; 18 else num = ch - '0'; 19 20 ch = getchar(); 21 22 while(ch >= '0' && ch <= '9') { 23 num = num * 10 + ch - '0'; 24 ch = getchar(); 25 } 26 27 x = num; 28 if(negative) 29 x = -x; 30 } 31 32 inline int lowbit(int x) { 33 return x & (-x); 34 } 35 36 inline int sum(int x) { 37 int ans = 0; 38 for(int i=x; i>0; i-=lowbit(i)) 39 ans += c[i]; 40 return ans; 41 } 42 43 inline void add(int x , int y) { 44 for(int i=x; i<=n; i+=lowbit(i)) 45 c[i] += y; 46 } 47 48 int main() { 49 50 read(n) , read(m); 51 for(int i=1; i<=n; i++) { 52 read(a[i]); 53 add(i,a[i]); 54 } 55 56 for(int i=1,z,x,y; i<=m; i++) { 57 read(z) , read(x) , read(y); 58 if(z == 1) add(x,y); 59 if(z == 2) printf("%d ",sum(y) - sum(x-1)); 60 } 61 62 return 0; 63 64 }
讲个笑话，树状数组的题都能用线段树短
那为什么我们还要树状数组呢？
当然是因为代码短、更好写了啦~
LCA 最近公共祖先问题
例题：戳我
LCA 是什么意思呢 Largest China Apple？
哦哦哦哦哦不对当然不是这样
求出最近公共祖先有什么tarjan算法，还要什么病茶几and check
本蒟蒻这里就不介绍了，这里介绍一个倍增的算法
倍增呢，是一个神奇的东西，就是把2^p化成2^(p-1) + 2^(p-1)
然后瞎**搞啦！
附上代码
1 // luogu-judger-enable-o2 2 #include <iostream> 3 #include <cstdio> 4 #include <cmath> 5 6 using namespace std; 7 8 const int Maxn = 500010; 9 int n , m , s , tot , maxdep; 10 int last[Maxn]; 11 int depth[Maxn]; /* depth[i] : i的深度 */ 12 int f[Maxn][20]; /* f[i][k] : i的第2^k祖先 */ 13 14 struct Edge { 15 int to; 16 int next; 17 } e[Maxn*2]; 18 19 inline void add(int u , int v) { 20 tot ++; 21 e[tot].to = v; 22 e[tot].next = last[u]; 23 last[u] = tot; 24 } 25 26 inline void dfs(int x , int fa) { 27 28 depth[x] = depth[fa] + 1; 29 maxdep = max(maxdep,depth[x]); 30 f[x][0] = fa; 31 32 for(register int i=1; (1<<i)<=depth[x]; i++) 33 f[x][i] = f[f[x][i-1]][i-1]; 34 /* x的第2^k祖先 = x的第2^(k-1)祖先的第2^(k-1)祖先 */ 35 36 for(register int i=last[x]; i; i=e[i].next) { 37 register int y = e[i].to; 38 if(y != fa) dfs(y,x); /* 遍历儿子 */ 39 } 40 41 } 42 43 inline int lca(int a , int b) { 44 45 if(a == b) return a; 46 if(depth[a] > depth[b]) swap(a,b); 47 48 for(register int i=maxdep; i>=0; i--) 49 if(depth[a] <= depth[b] - (1<<i)) 50 b = f[b][i]; 51 /* 一个数一定会由2^k+2^m+2^p+...组成 52 a的深度和b的深度的差距也一定会由2^k+2^m+2^p+...组成 53 所以最终一定会到同一层 */ 54 55 if(a == b) return a; 56 57 for(register int i=maxdep; i>=0; i--) { 58 if(f[a][i] == f[b][i]) continue; /* continue的作用是找a和b的最近祖先 */ 59 else a = f[a][i] , b = f[b][i]; 60 } 61 62 return f[a][0]; 63 64 } 65 66 int main() { 67 68 scanf("%d%d%d",&n,&m,&s); 69 for(register int i=1,x,y; i<n; i++) { 70 scanf("%d%d",&x,&y); 71 add(x,y); 72 add(y,x); 73 } 74 75 dfs(s,0); 76 77 maxdep = log2(maxdep); 78 for(register int u,v; m--; ) { 79 scanf("%d%d",&u,&v); 80 printf("%d ",lca(u,v)); 81 } 82 83 return 0; 84 85 }
这里插一句，集训的时候我们去了上海交♂大和上海纽扣大学啊呸
然后身份证丢了……为什么呢？无可奉告。
最后还是感谢海亮的老师们，帮我各种联系找到了身份证
就不用用半条命换钱包了
数论~
数论当然不是一个算法啦
当时就是万恶的数论害的我……哇呜呜呜呜不说了
这里说个exgcd，扩展欧几里得算法
证明可以说是能用几个词来形容了
就是 naive 显而易见 易证 轻松的得到了啦
啊呸啊呸我都说了什么
好了 我搞个板子下来 凑个字数啦~
1 template < typename Typ > 2 inline Typ exgcd(Typ a , Typ b , Typ &x , Typ &y) { 3 4 if(!b) { 5 x = (Typ)1; 6 y = (Typ)0; 7 return a; 8 } 9 10 register Typ Gcd = exgcd(b,a%b,x,y); 11 12 register Typ tmp = x; 13 x = y; 14 y = tmp - a / b * y; 15 16 return Gcd; 17 18 }
template那一行是什么意思呢？
一站式满足：戳我
没想到吧 ->此处省略邪笑
manacher和kmp算法
简称马拉车和看*片
你什么都没听到qwq
这两个算法是我见过的很玄学的算法
已经懒了，所以有代码qwq
先是马拉车
1 // luogu-judger-enable-o2 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 6 const int Maxn = 11000010; 7 char s[Maxn]; 8 int pal[2*Maxn]; 9 10 inline void read() { 11 12 register int len = -1; 13 register char ch = getchar(); 14 15 while(ch != EOF) { 16 s[++len] = ch; 17 ch = getchar(); 18 } 19 20 } 21 22 int main() { 23 24 read(); 25 26 register int len = strlen(s); 27 28 register int l = -1 , r = -1 , ans = 0; 29 30 for(register int z=0; z<2*len; z++) { 31 register int i = ( z + 1 ) >> 1; 32 register int j = z >> 1; 33 register int p = 0; 34 if(i < r) p = std :: min(r-i,pal[2*(l+r)-z]); 35 while(j+p+1 < len && i-p-1 >= 0 && s[j+p+1] == s[i-p-1]) p ++; 36 if (j + p > r) { 37 r = j + p; 38 l = i - p; 39 } 40 pal[z] = p; 41 register int tmp = 2 * p + 1; 42 if( z & 1 ) tmp --; 43 ans = std :: max(ans,tmp); 44 } 45 46 printf("%d ",ans); 47 48 return 0; 49 50 }
然后看*片
1 // luogu-judger-enable-o2 2 #include <iostream> 3 #include <cstdio> 4 5 using namespace std; 6 7 const int Maxn = 1000010; 8 int len1 , len2; 9 string x , y , a , b; 10 int next[Maxn]; 11 12 int main() { 13 14 cin >> a >> b; 15 16 len1 = a.size(); 17 len2 = b.size(); 18 19 x.resize(len1); 20 y.resize(len2); 21 22 for(register int i=1; i<=len1; i++) x[i] = a[i-1]; 23 for(register int i=1; i<=len2; i++) y[i] = b[i-1]; 24 25 next[1] = 0; 26 27 for(register int i=2,j=0; i<=len2; i++) { 28 while(j && y[i] != y[j+1]) j = next[j]; 29 if(y[i] == y[j+1]) j ++; 30 next[i] = j; 31 } 32 33 for(register int i=1,j=0; i<=len1; i++) { 34 while(j && x[i] != y[j+1]) j = next[j]; 35 if(x[i] == y[j+1]) j ++; 36 if(j == len2) { 37 printf("%d ",i-len2+1); 38 j = next[j]; 39 } 40 } 41 42 for(register int i=1; i<=len2; i++) 43 printf("%d ",next[i]); 44 putchar(' '); 45 46 return 0; 47 48 }
wow~我凑了好多字啦
啊呸啊呸没什么
下面讲一个非常容易理解的字符串算法
猜猜看是什么？
Trie树
简单介绍下，就是把字符串每个字符弄成个子节点，然后暴力遍历一遍就行了
模板题：戳我
没想到吧！题目名称这么怪
我又要想个借口贴模板啦！嗯就是这题比较简单
于是上~模~板~
1 // luogu-judger-enable-o2 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 6 using namespace std; 7 8 const int Maxn = 10010; 9 const int Son = 30; 10 int n , m , num; 11 struct Trie { 12 bool flag; 13 bool first; 14 int son[Son]; 15 } t[Maxn*50]; 16 17 inline void insert(string s) { 18 19 register int u = 0; 20 register int len = s.size(); 21 22 for(register int i=0; i<len; i++) { 23 register int v = int ( s[i] - 'a' + 1 ); 24 if(!t[u].son[v]) t[u].son[v] = ++ num; 25 u = t[u].son[v]; 26 } 27 28 t[u].flag = true; 29 30 } 31 32 inline int query(string s) { 33 34 register int u = 0; 35 register int len = s.size(); 36 register int state = 0; 37 38 for(register int i=0; i<len; i++) { 39 register int v = int ( s[i] - 'a' + 1 ); 40 if(!t[u].son[v]) return 1; 41 u = t[u].son[v]; 42 } 43 44 if(!t[u].flag) return 1; 45 if(t[u].first) return 2; 46 t[u].first = true; 47 return 0; 48 49 } 50 51 int main() { 52 53 register string name; 54 55 scanf("%d",&n); 56 for(register int i=1; i<=n; i++) { 57 cin >> name; 58 insert(name); 59 } 60 scanf("%d",&m); 61 for(; m--; ) { 62 cin >> name; 63 register int state = query(name); 64 if(!state) puts("OK"); 65 else if(state == 1) puts("WRONG"); 66 else puts("REPEAT"); 67 } 68 69 return 0; 70 71 }
全新算法：AC自动机
这个算法很神奇，只要交上去就会自动A题，分分钟成为Rank1，妈妈再也不用担心我的OI生活啦
等下。。。看错算法了，那个算法是自动AC机QWQ
这个算法呢，就是要你熟练的掌握看*片算法和Trie树
然后结合起来跑一遍就行了
有2道模板题：
不用说的啦~先附上代码~
简单版：
1 // luogu-judger-enable-o2 2 #include <iostream> 3 #include <cstdio> 4 #include <queue> 5 6 using namespace std; 7 8 const int Maxn = 1000010; 9 const int Maxm = 30; 10 int n , cnt; 11 12 struct Trie { 13 int fail; 14 int end; 15 int num[Maxm]; 16 } t[Maxn]; 17 18 inline void Build(string s) { 19 20 register int len = s.size(); 21 register int now = 0; 22 23 for(register int i=0; i<len; i++) { 24 register int to = s[i] - 'a' + 1; 25 if(!t[now].num[to]) t[now].num[to] = ++ cnt; 26 now = t[now].num[to]; 27 } 28 29 t[now].end ++; 30 31 } 32 33 inline void Getfail() { 34 35 queue <int> Q; 36 37 for(register int i=1; i<=26; i++) { 38 if(t[0].num[i]) { 39 t[t[0].num[i]].fail = 0; 40 Q.push(t[0].num[i]); 41 } 42 } 43 44 while(!Q.empty()) { 45 register int now = Q.front(); 46 Q.pop(); 47 for(register int i=1; i<=26; i++) { 48 if(t[now].num[i]) { 49 t[t[now].num[i]].fail = t[t[now].fail].num[i]; 50 Q.push(t[now].num[i]); 51 } else t[now].num[i] = t[t[now].fail].num[i]; 52 } 53 } 54 55 } 56 57 inline int Query(string s) { 58 59 register int len = s.size(); 60 register int now = 0 , ans = 0; 61 62 for(register int i=0; i<len; i++) { 63 register int to = s[i] - 'a' + 1; 64 now = t[now].num[to]; 65 for(register int j=now; j&&t[j].end; j=t[j].fail) { 66 ans += t[j].end; 67 t[j].end = 0; 68 } 69 } 70 71 return ans; 72 73 } 74 75 int main() { 76 77 register string s; 78 79 scanf("%d",&n); 80 for(register int i=1; i<=n; i++) { 81 cin >> s; 82 Build(s); 83 } 84 85 t[0].fail = 0; 86 87 Getfail(); 88 89 cin >> s; 90 91 cout << Query(s) << endl; 92 93 return 0; 94 95 }
吐槽一句luogu数据貌似有点水嗯哼
现在来提高版：
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <queue> 6 7 using namespace std; 8 9 const int Maxn = 100010; 10 const int Maxm = 30; 11 int n , cnt; 12 string s[Maxn]; 13 queue <int> Q; 14 15 struct Trie { 16 int fail; 17 int end; 18 int num[Maxm]; 19 } t[Maxn]; 20 21 struct Str { 22 int id; 23 int tot; 24 } a[Maxn]; 25 26 inline void Clean(int x) { 27 28 t[x].end = t[x].fail = 0; 29 for(register int i=1; i<=26; i++) 30 t[x].num[i] = 0; 31 32 } 33 34 inline bool comp(const Str &x , const Str &y) { 35 if(x.tot > y.tot) return true; 36 if(x.tot < y.tot) return false; 37 return x.id < y.id; 38 } 39 40 inline void Build(string s , int idx) { 41 42 register int len = s.size(); 43 register int now = 0; 44 45 for(register int i=0; i<len; i++) { 46 register int to = s[i] - 'a' + 1; 47 if(!t[now].num[to]) { 48 t[now].num[to] = ++ cnt; 49 Clean(cnt); 50 } 51 now = t[now].num[to]; 52 } 53 54 t[now].end = idx; 55 56 } 57 58 inline void Getfail() { 59 60 while(!Q.empty()) Q.pop(); 61 62 for(register int i=1; i<=26; i++) { 63 if(t[0].num[i]) { 64 t[t[0].num[i]].fail = 0; 65 Q.push(t[0].num[i]); 66 } 67 } 68 69 while(!Q.empty()) { 70 register int now = Q.front(); 71 Q.pop(); 72 for(register int i=1; i<=26; i++) { 73 if(t[now].num[i]) { 74 t[t[now].num[i]].fail = t[t[now].fail].num[i]; 75 Q.push(t[now].num[i]); 76 } else t[now].num[i] = t[t[now].fail].num[i]; 77 } 78 } 79 80 } 81 82 inline void Query(string s) { 83 84 register int len = s.size(); 85 register int now = 0; 86 87 for(register int i=0; i<len; i++) { 88 register int to = s[i] - 'a' + 1; 89 now = t[now].num[to]; 90 for(register int j=now; j; j=t[j].fail) 91 a[t[j].end].tot ++; 92 } 93 94 } 95 96 int main() { 97 98 while(scanf("%d",&n) != EOF) { 99 100 if(!n) return 0; 101 102 cnt = 0; 103 Clean(0); 104 105 for(register int i=1; i<=n; i++) { 106 cin >> s[i]; 107 a[i].id = i; 108 a[i].tot = 0; 109 Build(s[i],i); 110 } 111 112 Getfail(); 113 114 cin >> s[0]; 115 Query(s[0]); 116 117 sort(a+1,a+n+1,comp); 118 119 printf("%d ",a[1].tot); 120 cout << s[a[1].id] << endl; 121 for(register int i=2; i<=n; i++) { 122 if(a[i].tot != a[i-1].tot) break; 123 cout << s[a[i].id] << endl; 124 } 125 126 } 127 128 return 0; 129 130 }
其实提高版不难，加个排序等奇奇gaygay的操作就行了QVQ
哦对了，这些字符串算法全是一个dalao讲的
在这里我要疯狂%%%%%%%飞神
我能记起来的最后一个算法：
差分约束
其实这个就是个转成SPFA的算法
利用三角形不等式，dis[i] + e[i].w < dis[j] 然后……
还有各种判环就行了啦~so~easy~
模板题：戳我
附上代码~
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 5 using namespace std; 6 7 typedef long long ll; 8 const int Maxn = 100010; 9 int n , m , tot; 10 int repeat[Maxn]; 11 int last[Maxn]; 12 int dis[Maxn]; 13 bool vis[Maxn]; 14 15 struct Edge { 16 int to; 17 int w; 18 int next; 19 } e[(Maxn<<1)+Maxn]; 20 21 queue < int > Q; 22 23 template < typename Typ > 24 inline void read(Typ &x) { 25 26 register Typ num = 0; 27 register char ch = getchar(); 28 29 while(ch < '0' || ch > '9') ch = getchar(); 30 31 while(ch >= '0' && ch <= '9') { 32 num = ( num << 3 ) + ( num << 1 ) + ch - '0'; 33 ch = getchar(); 34 } 35 36 x = num; 37 38 } 39 40 inline void add(int u , int v , int w) { 41 tot ++; 42 e[tot].to = v; 43 e[tot].w = w; 44 e[tot].next = last[u]; 45 last[u] = tot; 46 } 47 48 inline bool Spfa(int s) { 49 50 while(!Q.empty()) Q.pop(); 51 vis[s] = true; 52 Q.push(s); 53 54 while(!Q.empty()) { 55 register int u = Q.front(); 56 Q.pop(); 57 vis[u] = false; 58 for(register int i=last[u]; i; i=e[i].next) { 59 register int v = e[i].to; 60 if(dis[u] + e[i].w > dis[v]) { 61 repeat[v] ++; 62 if(repeat[v] >= n) return false; 63 dis[v] = dis[u] + e[i].w; 64 if(!vis[v]) { 65 vis[v] = true; 66 Q.push(v); 67 } 68 } 69 } 70 } 71 72 return true; 73 74 } 75 76 inline ll getsum() { 77 78 register ll sum = 0; 79 80 for(register int i=1; i<=n; i++) 81 sum += dis[i]; 82 83 return sum; 84 85 } 86 87 int main() { 88 89 read(n) , read(m); 90 for(register int x,y,z; m--; ) { 91 read(z) , read(x) , read(y); 92 if(z == 1) add(x,y,0) , add(y,x,0); 93 if(z == 2) { 94 if(x == y) return !puts("-1"); 95 add(x,y,1); 96 } 97 if(z == 3) add(y,x,0); 98 if(z == 4) { 99 if(x == y) return !puts("-1"); 100 add(y,x,1); 101 } 102 if(z == 5) add(x,y,0); 103 } 104 105 for(register int i=n; i>=1; i--) 106 add(0,i,1); 107 108 register bool tmp = Spfa(0); 109 if(!tmp) puts("-1"); 110 else printf("%lld ",getsum()); 111 112 return 0; 113 114 }
好了~
我觉得总结好了呢~
可是并没有呢~
等到集训结束后我们再见面吧~
By BlueCat