差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:图论_1 [2020/07/15 10:24]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:图论_1 [2020/08/01 00:05] (当前版本)
jxm2001
@@ 行 39: / 行 39: @@
 </code>
-=== 例题 ===
+=== 例题 1 ===
 [[https://www.luogu.com.cn/problem/P1462|洛谷p1462]]
@@ 行 57: / 行 57: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e4+5,MAXM=5e4+5,Inf=2e9;
 struct Edge{
@@ 行 173: / 行 126: @@
 	else
 	puts("AFK");
+	return 0;
+}
+</code>
+</hidden>
+=== 例题 2 ===
+[[https://ac.nowcoder.com/acm/contest/5667/I|牛客暑期多校(第二场) I 题]]
+== 题意 ==
+给定一个区间，可执行一下操作：
+   - $[x,y]\to [x+1,y](x\lt y)$
+   - $[x,y]\to [x,y-1](x\lt y)$
+   - $[x,y]\to [x-1,y](x\gt 1)$
+   - $[x,y]\to [x,y+1](y\lt n)$
+给定一些第 $1,2$ 类操作的禁令，每条禁令花费 $c_i$。
+考虑选择从中选择部分禁令，使得区间 $[1,n]$ 无法变换为 $[x,x](1\lt x\lt n)$，且总花费最少。
+== 题解 ==
+考虑建立 $L-R$ 坐标系，题目等价于不能从 $(1,n)$ 跑到直线 $L=R$。把每个网格当成节点，每条禁令连接两个网格。
+取最右边为超级源点，最上边为超级汇点，跑最短路算法即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=505*505;
+const LL Inf=1e12;
+struct Edge{
+	int to,w,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,w,head[u]};
+	head[u]=edge_cnt;
+}
+template <typename T>
+struct dijkstra{
+	T dis[MAXN];
+	bool vis[MAXN];
+	priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >q;
+	void solve(int src,int n){
+		mem(vis,0);
+		_rep(i,1,n)
+		dis[i]=Inf;
+		dis[src]=0;
+		q.push(make_pair(dis[src],src));
+		while(!q.empty()){
+			pair<T,int> temp=q.top();q.pop();
+			int u=temp.second;
+			if(vis[u])
+			continue;
+			vis[u]=true;
+			for(int i=head[u];i;i=edge[i].next){
+				int v=edge[i].to;
+				if(dis[v]>edge[i].w+dis[u]){
+					dis[v]=edge[i].w+dis[u];
+					q.push(make_pair(dis[v],v));
+				}
+			}
+		}
+	}
+};
+dijkstra<LL> solver;
+int n,m;
+int Id(int r,int c){return (r-1)*(n-1)+c;}
+int main()
+{
+	n=read_int(),m=read_int();
+	int s=Id(n-1,n-1)+1,t=s+1;
+	int r,c,w,id1,id2;char d;
+	while(m--){
+		c=read_int(),r=read_int(),d=get_char(),w=read_int();
+		id1=Id(r-1,c);
+		if(d=='L'){
+			if(r==n)
+			id2=t;
+			else
+			id2=Id(r,c);
+		}
+		else{
+			if(c==1)
+			id2=s;
+			else
+			id2=Id(r-1,c-1);
+		}
+		Insert(id1,id2,w);Insert(id2,id1,w);
+	}
+	solver.solve(s,t);
+	if(solver.dis[t]==Inf)
+	puts("-1");
+	else
+	enter(solver.dis[t]);
 	return 0;
 }
@@ 行 248: / 行 297: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e4+5,MAXM=5e5+5,Inf=1e9;
 struct Edge{
@@ 行 401: / 行 403: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=200+5,Inf=1e9;
 int dis[MAXN][MAXN],t[MAXN];
@@ 行 505: / 行 460: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=3e3+5,MAXM=9e3+5,Inf=1e9;
 struct Edge{
@@ 行 687: / 行 595: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=105,MAXM=1005,Inf=1e9;
 struct Edge{
@@ 行 989: / 行 850: @@
   * 任意两个双连通分量间无公共点和公共边
-求边-双连通分量有两种方法，与求点-双连通分量类似。
+求边-双连通分量有两种方法，与求点-双连通分量类似。一般考虑先一次 $\text{dfs}$ 求出桥，再一次 $\text{dfs}$ 染色，染色过程中不经过桥。
-=== 例题 ===
+使用上述方法求边-双连通分量时需要注意标记桥时需要将双向边同时标记，如果只标记了双向边的某一条边，染色过程中可能出现错误。
+=== 例题 1 ===
 [[https://www.luogu.com.cn/problem/P3225|洛谷p3225]]
@@ 行 1015: / 行 878: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=505,MAXM=505;
 struct Edge{
@@ 行 1156: / 行 972: @@
 		printf("Case %d: %d %llu\n",++kase,ans1,ans2);
 	}
+	return 0;
+}
+</code>
+</hidden>
+=== 例题 2 ===
+[[https://codeforces.com/contest/1389/problem/G|edu 92 G题]]
+== 题意 ==
+给定 $n$ 个点 $m$ 条边的无向图，其中 $k$ 个点为特殊点，每个点有一个点权，每条边有一个边权。
+要求给无向图的边定向，如果将某条边定向为单向边，则不需要支付费用。如果将某条边定向为双向边，则需要支付等于该边边权的费用。
+定义图中的某个点为满足当且仅当所有特殊点可以到达沿有向边到达该点，且如果某个边成为满点，则可以获得等于该点点权的利润。
+要求输出 $n$ 个数，表示如果第 $i$ 个点为满点能得到的最大收益，其中收益 $=$ 利润 $-$ 费用。
+== 题解 ==
+有结论：对边双连通分量，存在某种策略可以将无向边全部定向为单向边并可以得到强连通分量。
+于是求出所有边双连通分量并缩点，得到一棵无根树，树上的边为原图的桥，接下来考虑树形 $\text{dp}$。
+先考虑如何求出第 $1$ 个节点为满点时的最大收益。(这里及下文的节点均指缩点后的节点)
+令第 $1$ 个节点为根节点，设 $\text{dp}(u)$ 为在第 $1$ 个节点为满点且为根节点的前提下 $u$ 是满点时 $u$ 所在子树利益的最大值。
+首先 $\text{dp}(u)$ 的初值为 $u$ 缩点中所有点的点权和。接下来考虑状态转移，假设节点 $u$ 为满点，考虑它的子节点 $v$。
+如果所有特殊点都在子节点 $v$ 的子树中，则 $v$ 一定是满点且连一条 $v\to u$ 的单向边，于是 $\text{dp}(u)\gets \text{dp}(v)$。
+如果所有特殊点都不在子节点 $v$ 的子树中，则贪心连一条 $u\to v$ 的单向边一定最优，于是 $\text{dp}(u)\gets \text{dp}(v)$。
+除了上面两种特殊情况，则由于子节点 $v$ 的子树中存在特殊节点，且  $u$ 为满点，所以必须能从 $v$ 走到 $u$。
+于是要么 $v$ 连一条单向边到 $u$，这样 $v$ 不是满点，对 $u$ 无贡献。要么 $v,u$ 间连一条双向边，于是贡献为 $dp(v)-w(u,v)$。
+所以该情况下有状态转移方程 $dp(u)=\max(0,dp(v)-w(u,v))$。
+根据上述方法，可以 $O(n)$ 求解第 $1$ 个节点为满点时的最大收益，接下来考虑换根 $\text{dp}$。
+不断转移根，假设当前根为 $u$，$v$ 为 $u$ 的子节点。
+于是先减去 $v$ 对 $u$ 的贡献，这样树被分成了以 $u$ 为根节点的树和以 $v$ 为根节点的树这两棵树。
+然后考虑将 $u$ 节点转化为 $v$ 的子节点并计算贡献。
+换根采用 $\text{dfs}$ 过程且需要回溯。总时间复杂度 $O(n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5;
+struct Edge{
+	int from,to,id,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int idx){
+	edge[++edge_cnt]=Edge{u,v,idx,head[u]};
+	head[u]=edge_cnt;
+}
+int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_sp[MAXN],bcc_cnt;
+bool is_bridge[MAXN];
+LL bcc_v[MAXN],dp[MAXN],ans[MAXN];
+vector<int> bcc[MAXN];
+vector<pair<int,int> >g[MAXN];
+int k,c[MAXN],node_sp[MAXN],edge_w[MAXN];
+void dfs(int u,int fa){
+	low[u]=dfs_id[u]=++dfs_t;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		if(!dfs_id[v]){
+			dfs(v,u);
+			low[u]=min(low[u],low[v]);
+			if(low[v]>dfs_id[u])
+			is_bridge[edge[i].id]=true;
+		}
+		else
+		low[u]=min(low[u],dfs_id[v]);
+	}
+}
+void dfs_2(int u,int fa){
+	bcc_id[u]=bcc_cnt;
+	bcc_v[bcc_cnt]+=c[u];
+	bcc_sp[bcc_cnt]+=node_sp[u];
+	bcc[bcc_cnt].push_back(u);
+	for(int i=head[u];i;i=edge[i].next){
+		if(is_bridge[edge[i].id])continue;
+		int v=edge[i].to;
+		if(v==fa||bcc_id[v])continue;
+		dfs_2(v,u);
+	}
+}
+void get_bcc(int n){
+	dfs(1,1);
+	_rep(i,1,n){
+		if(!bcc_id[i]){
+			bcc_cnt++;
+			dfs_2(i,i);
+		}
+	}
+	_rep(i,1,edge_cnt){
+		if(is_bridge[edge[i].id]){
+			int u=bcc_id[edge[i].from],v=bcc_id[edge[i].to];
+			g[u].push_back(make_pair(v,edge_w[edge[i].id]));
+		}
+	}
+}
+void update_edge(int u,int v,int d,int w){
+	LL t=dp[v];
+	if(bcc_sp[v]>0&&bcc_sp[v]<k)
+	t=max(0LL,dp[v]-w);
+	dp[u]+=d*t;
+	bcc_sp[u]+=d*bcc_sp[v];
+}
+void dp_1(int u,int fa){
+	dp[u]=bcc_v[u];
+	_for(i,0,g[u].size()){
+		int v=g[u][i].first,w=g[u][i].second;
+		if(v==fa)continue;
+		dp_1(v,u);
+		update_edge(u,v,1,w);
+	}
+}
+void dp_2(int u,int fa){
+	ans[u]=dp[u];
+	_for(i,0,g[u].size()){
+		int v=g[u][i].first,w=g[u][i].second;
+		if(v==fa)continue;
+		update_edge(u,v,-1,w);
+		update_edge(v,u,1,w);
+		dp_2(v,u);
+		update_edge(v,u,-1,w);
+		update_edge(u,v,1,w);
+	}
+}
+int main()
+{
+	int n,m,u,v;
+	n=read_int(),m=read_int(),k=read_int();
+	_rep(i,1,k)
+	node_sp[read_int()]=1;
+	_rep(i,1,n)
+	c[i]=read_int();
+	_rep(i,1,m)
+	edge_w[i]=read_int();
+	_rep(i,1,m){
+		u=read_int(),v=read_int();
+		Insert(u,v,i);Insert(v,u,i);
+	}
+	get_bcc(n);
+	dp_1(1,1);
+	dp_2(1,1);
+	_rep(i,1,n)
+	space(ans[bcc_id[i]]);
 	return 0;
 }
@@ 行 1279: / 行 1253: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=2e5+5,MAXM=1e5+5;
 struct Edge{

CVBB ACM Team

用户工具

站点工具

差别

页面工具