@ysner
2018-09-25T09:29:25.000000Z
字数 2185
阅读 1986
总结 图论
判负环有个比较快的方法：记录经过当前点的当前最短路被更新了多少次，如果超过次就确认有负环。
queue<int>Q;il int SPFA(){while(!Q.empty()) Q.pop();fp(i,1,n) dis[i]=0,vis[i]=1,f[i]=0,Q.push(i);while(!Q.empty()){re int u=Q.front();Q.pop();for(re int i=h[u];i+1;i=e[i].nxt){re int v=e[i].to;if(dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;f[v]=f[u]+1;//记录被更新多少次if(f[v]>=n+1) return 1;if(!vis[v]) vis[v]=1,Q.push(v);}}vis[u]=0;}return 0;}
给你一条数轴和条线段，第条线段覆盖区间，选择它需要代价。请选出代价和最小的一组线段使得区间中的每一段都被覆盖。
解析：
这种问题不需要。
可以从向连权值为的有向边，再从向连权值为的有向边（因为可以重复覆盖），再跑最短路即可。
有个未知量，对对未知量，有要求，，如何建边？
解析：
若题目中询问两个量的最大差值，
则建边意义应为：，则建边，权值为；
对怎么处理？
两边同时取反，得，则建边，权值为即可。
算法：
每次对于每个连通块找一条连接这个连通块和另外某个连通块的最小边，加入这些边。可以发现每次连通块的数目都至少会/2，因此时间复杂度O(nlog(n)*找出所求的边的复杂度)。
这个玩意一般与位运算结合。
给个例子：[[CF888G]Xor-MST][1]
没有奇环的图叫二分图。
判断二分图的方法：黑白染色。
如果有奇环，会发现某个已走过的点将染上不同的颜色。
匈牙利算法。
一个匹配增广的过程。
核心思想：在原来匹配完的点还能匹配到别的点的前提下，让现在的点匹配其对偶。
il int dfs(re int u){for(re int i=h[u];i+1;i=e[i].nxt){re int v=e[i].to;if(!vis[v]){vis[v]=1;if(!link[v]||dfs(link[v])) {link[v]=u;return 1;}}}return 0;}fp(i,1,n){memset(vis,0,sizeof(vis));ans+=dfs(i);}
关押罪犯
方法不少：
其实就是一个罪犯应该出现在另一个罪犯的补集中。
每次并查集将两者并入对方的补集。
如果发现两者在同一补集中就凉了。
从大到小加入每一条边，想办法快速判断这张图是否是二分图。在这里介绍一种应用较为广泛的方法：带权并查集。
设表示从到并查集的根节点的路径的长度的奇偶性。
对于一条新边，若不在同一联通块，直接连；
否则如果间路径长度为偶数，就凉了。
这个可以通过跳并差集父亲来算。
割点模板。没有,同时注意特判当前根结点。
il void Tarjan(re int u){dfn[u]=low[u]=++tot;for(re int i=h[u];i+1;i=e[i].nxt){re int v=e[i].to;if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u])if(u^rt) cut[u]=1;else ++gu;}else low[u]=min(low[u],dfn[v]);}if(u==rt&&gu>1) cut[u]=1;}int main(){memset(h,-1,sizeof(h));n=gi();m=gi();fp(i,1,m){re int u=gi(),v=gi();add(u,v);add(v,u);}fp(i,1,n) if(!dfn[i]) gu=0,Tarjan(rt=i);tot=0;fp(i,1,n) if(cut[i]) ++tot;printf("%d\n",tot);fp(i,1,n) if(cut[i]) printf("%d ",i);puts("");return 0;}