图论_2。

有一道不错的图论：P2149 [SDOI2009] Elaxia的路线，学习了一下大佬的想法，先正反跑四遍最短路，然后肯定他们交互的边在其中出现，那么，明显还有一个结论，就是倘若一条边在一条最短路之中，那么肯定两个端点分别到起点与终点的距离+其长度==最短路的长度，自己画图想想，绝妙，那么我们就可以正反跑四遍来求出距离之后枚举就行了，最后套一个拓扑操作方案是——若是我这条边能被加入，那么就加入并使其取最大值。注意要正做一遍反做一遍。
为什么要正做一次反做一次呢，是因为，可能会倒着走，两个人从不同方向走同一条边也算满足条件。所以正反都要做。

#include
#define int long long 
using namespace std;
int n,m,len=0,last[1000001],dis[1000001][5],INF=1000010000;
bool v[2000001];
int to[1000001],in[1000001],f[1000001],g[1000001];
struct pp
{
	int x,y,c,next;
};pp p[2500250];
struct node
{
	int x,dis;
	friend bool operator < (const node &x,const node &y)
	{
		return x.dis > y.dis;
	};
};priority_queue<node > q;
void ins(int x,int y,int c)
{
	int now=++len;
	p[now]={x,y,c,last[x]};last[x]=now;
	return ;
}
void dj(int ST,int k)
{
	for(int i=1;i<=n;i++) dis[i][k]=INF,v[i]=false;dis[ST][k]=0; 
	node e;e.dis=dis[ST][k],e.x=ST;q.push(e);
	while(q.size())
	{
		node x=q.top();q.pop();if(v[x.x]) continue ;v[x.x]=true;
		for(int i=last[x.x];i!=-1;i=p[i].next)
		{
			int y=p[i].y;
			if(dis[y][k]>dis[x.x][k]+p[i].c) 
			{
				dis[y][k]=dis[x.x][k]+p[i].c;
				e.dis=dis[y][k],e.x=y;q.push(e);
			}
		}
	}
	while(q.size()) q.pop();
	return ;	 	
} 
int st1,st2,ed1,ed2;
signed main()
{
	memset(last,-1,sizeof(last));
	scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&st1,&ed1,&st2,&ed2);
	for(int i=1;i<=m;i++)
	{
		int x,y,c;scanf("%lld%lld%lld",&x,&y,&c);
		ins(x,y,c);ins(y,x,c);
	}
	dj(st1,0);dj(ed1,1);dj(st2,2);dj(ed2,3);memset(v,false,sizeof(v));
	for(int x=1;x<=n;x++)
	{
		for(int i=last[x];i!=-1;i=p[i].next)
		{
			int y=p[i].y;
			if(p[i].c+dis[x][0]+dis[y][1]==dis[ed1][0]) in[y]++,v[i]=true;
		}
	}
	int st=1,ed=1,ans=0;to[ed++]=st1;
	while(st!=ed)
	{
		int x=to[st++];ans=max(ans,max(f[x],g[x]));
		for(int i=last[x];i!=-1;i=p[i].next)
		{
			int y=p[i].y;if(!v[i]) continue ;
			in[y]--;if(!in[y]) to[ed++]=y;//printf("%d %d\n");
			if(dis[x][2]+p[i].c+dis[y][3]==dis[ed2][2]) f[y]=max(f[y],f[x]+p[i].c);
			if(dis[x][3]+p[i].c+dis[y][2]==dis[ed2][2]) g[y]=max(g[y],g[x]+p[i].c); 
		}
	}
	printf("%lld",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

割点好题？P5058 [ZJOI2004]嗅探器

#include
using namespace std;
int n,m,len=0,last[500005],dfsx[500005],low[500005],dfs_x=0,ans[500005];
int a,b;
struct pp
{
	int x,y,next;
};pp p[2000005];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void CNT(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) 
		{
			CNT(y),low[x]=min(low[x],low[y]);
			if(dfsx[x]<=low[y]&&x!=a&&dfsx[b]>=dfsx[y]) ans[x]=1; 
		}
		low[x]=min(low[x],dfsx[y]);
	}
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));
	scanf("%d",&n);
	int x,y;while(scanf("%d%d",&x,&y))
	{
		if(x==0&&y==0) break ;
		ins(x,y);ins(y,x);	
	}	
	scanf("%d%d",&a,&b);
	CNT(a);
	for(int i=1;i<=n;i++) 
	{
		if(ans[i])
		{
			printf("%d",i);
			return 0;
		}
	}
	printf("No solution");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

P3469 [POI2008]BLO-Blockade，讨论两种情况，如果点x是不是割点，那么贡献是2*（n-1），因为一个点与余下所有点的匹配就是这样的啦（注意这里要求是有序点对，所以是乘二） ,那么可能要是割点的话呢，那么就要讨论一下，被割出去了的点，剩下的环（联通块），剩下的那一个点。然后就算一下就行。

#include
#define int long long
using namespace std;
int n,m,len=0,last[5000001],dfsx[5000001],low[5000001],dfs_x=0;
int siz[5000001],ans[5000001],cnt[5000001];
struct pp
{
	int x,y,next;
};pp p[5000001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void CNT(int x,int dd)
{
	dfsx[x]=low[x]=++dfs_x;siz[x]=1;
	int sum=0,ch=0,pd=0;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) 
		{
			CNT(y,dd);
			low[x]=min(low[x],low[y]);
			siz[x]+=siz[y];
			if(dfsx[x]<=low[y])
			{//printf("**%d\n",x);
				ans[x]+=(siz[y]*(n-siz[y]));
				sum+=siz[y];
				if(x==dd) ch++;
				else pd=1;
			}
		}
		else low[x]=min(low[x],dfsx[y]);
	}
	if(pd||(ch>=2)) ans[x]+=(n-sum-1)*(sum+1)+(n-1);
	else ans[x]=(n-1)*2;
	return ;
}
signed main()
{
	memset(last,-1,sizeof(last));
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++) 
	{
		int x,y;scanf("%lld%lld",&x,&y);
		ins(x,y);ins(y,x); 
	}
	CNT(1,1);
	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

谈一谈分层图P4822 [BJWC2012]冻结，建图的方式其实是和网络流那种差不多的不过就是有一些差别。考虑每一个k的贡献，我们还是被局限了，你太过于关注于每次的最优解，而不是全局的，这才是你次次失利的原因，考虑让其内部解决，我们只需要统计最小值，具体而言，对于每一个点可以向下一层建距离一半的边k条，那就行了，然后直接统计答案。具体的看看代码？主要是思想哦

#include
using namespace std;
int n,m,len=0,last[4000001],dis[4000001],k;
bool v[4000001];
struct pp
{
	int x,y,c,next;
};pp p[4000001];
struct node 
{
	int x,dis;
	friend bool operator < (const node &x,const node &y)
	{
		return x.dis>y.dis;	
	};
};priority_queue<node> q;

void ins(int x,int y,int c)
{
	int now=++len;
	p[now]={x,y,c,last[x]};last[x]=now;
	return ;
}
int dj(int ST)
{
	memset(dis,63,sizeof(dis));memset(v,false,sizeof(v));
	dis[ST]=0;node e;e.dis=dis[ST],e.x=ST;q.push(e);
	while(q.size())
	{//printf("*");
		node x=q.top();q.pop();if(v[x.x]) continue ;v[x.x]=true ;
		for(int i=last[x.x];i!=-1;i=p[i].next)
		{//	printf("%d %d %d\n",dis[p[i].y],dis[x.x],p[i].c);
			int y=p[i].y;if(dis[y]<dis[x.x]+p[i].c) continue ;
			dis[y]=dis[x.x]+p[i].c;e.x=y,e.dis=dis[y];q.push(e);
		}
	}
	int minn=1e9;
	for(int i=1;i<=k+1;i++) minn=min(minn,dis[i*n]);
	return minn;
}
int main()
{
	memset(last,-1,sizeof(last));
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int x,y,c;scanf("%d%d%d",&x,&y,&c);
		for(int j=0;j<=k;j++) ins(j*n+x,j*n+y,c),ins(j*n+y,j*n+x,c);
		for(int j=0;j<k;j++) ins(j*n+x,(j+1)*n+y,c/2),ins(j*n+y,(j+1)*n+x,c/2);
	}
	printf("%d",dj(1));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

P4568 [JLOI2011] 飞行路线呃你要是看出来是分层图的话大概不难？

#include
using namespace std;
int n,m,k,len=0,last[5000001],dis[5000001];
bool v[5000001];
struct pp
{
	int x,y,c,next;
};pp p[10000001];
struct node 
{
	int x,dis;
	friend bool operator < (const node &x,const node &y)
	{
		return x.dis>y.dis;
	};
};priority_queue<node > q;
void ins(int x,int y,int c)
{
	int now=++len;
	p[now]={x,y,c,last[x]};last[x]=now;
	return ;
}
int dj(int ST,int ED)
{
	memset(dis,63,sizeof(dis));memset(v,false,sizeof(v));dis[ST]=0;
	node e;e.dis=dis[ST],e.x=ST;q.push(e);
	while(q.size())
	{//printf("*");
		node x=q.top();q.pop();if(v[x.x]) continue ;v[x.x]=true ;
		for(int i=last[x.x];i!=-1;i=p[i].next)
		{
			int y=p[i].y;if(dis[y]<dis[x.x]+p[i].c) continue ;
			dis[y]=dis[x.x]+p[i].c;e.dis=dis[y],e.x=y;q.push(e);
		}
	}
	int minn=1e9;
	for(int i=0;i<=k;i++) minn=min(minn,dis[ED+i*n]);
	return minn;
}
int main()
{ 
	memset(last,-1,sizeof(last));
	scanf("%d%d%d",&n,&m,&k);
	int ST,ED;scanf("%d%d",&ST,&ED);ST++,ED++;//printf(">>%d %d\n",ST,ED);
	for(int i=1;i<=m;i++)
	{
		int x,y,c;scanf("%d%d%d",&x,&y,&c);x++,y++;
		for(int i=0;i<=k;i++) ins(i*n+x,i*n+y,c),ins(i*n+y,i*n+x,c);
		for(int i=0;i<k;i++) ins(i*n+x,(i+1)*n+y,0),ins(i*n+y,(i+1)*n+x,0);
	}
	printf("%d",dj(ST,ED));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

P2939 [USACO09FEB]Revamping Trails G

#include
using namespace std;
int n,m,k,len=0,last[5000001],dis[5000001];
bool v[5000001];
struct pp
{
	int x,y,c,next;
};pp p[10000001];
struct node 
{
	int x,dis;
	friend bool operator < (const node &x,const node &y)
	{
		return x.dis>y.dis;
	};
};priority_queue<node > q;
void ins(int x,int y,int c)
{
	int now=++len;
	p[now]={x,y,c,last[x]};last[x]=now;
	return ;
}
int dj(int ST,int ED)
{
	memset(dis,63,sizeof(dis));memset(v,false,sizeof(v));dis[ST]=0;
	node e;e.dis=dis[ST],e.x=ST;q.push(e);
	while(q.size())
	{//printf("*");
		node x=q.top();q.pop();if(v[x.x]) continue ;v[x.x]=true ;
		for(int i=last[x.x];i!=-1;i=p[i].next)
		{
			int y=p[i].y;if(dis[y]<dis[x.x]+p[i].c) continue ;
			dis[y]=dis[x.x]+p[i].c;e.dis=dis[y],e.x=y;q.push(e);
		}
	}
	int minn=1e9;
	for(int i=0;i<=k;i++) minn=min(minn,dis[ED+i*n]);
	return minn;
}
int main()
{ 
	memset(last,-1,sizeof(last));
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		int x,y,c;scanf("%d%d%d",&x,&y,&c);
		for(int i=0;i<=k;i++) ins(i*n+x,i*n+y,c),ins(i*n+y,i*n+x,c);
		for(int i=0;i<k;i++) ins(i*n+x,(i+1)*n+y,0),ins(i*n+y,(i+1)*n+x,0);
	}
	int ST=1,ED=n;
	printf("%d",dj(ST,ED));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

下面隆重介绍一道超强的题目：P3119 [USACO15JAN]Grass Cownoisseur G缩点后套一个分层图+最短路。码量很大，你要忍一下。

#include
using namespace std;
int n,m,len=0,last[200001],dfsx[200001],low[200001],dfs_x=0,id[200001],point=0;
int q[800001],tot=0,siz[200001],k,dis[200001];
bool v[800001];
struct pp
{
	int x,y,next;
};pp p[800001],L[800001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
bool cmp(const pp &x,const pp &y)
{
	if(x.x!=y.x) return x.x<y.x;
	return x.y<y.y;
}
void SH(int x)
{
	low[x]=dfsx[x]=++dfs_x;
	v[x]=true;q[++tot]=x;//printf("*");
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) SH(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],dfsx[y]);
	}
	if(dfsx[x]==low[x])
	{
		point++;
		while(dfsx[x]<=dfsx[q[tot]])
		{	
			siz[point]++;id[q[tot]]=point;
			v[q[tot]]=false;tot--,dfs_x--;
		}
	}
	return ;
}
void remake()
{
	memset(last,-1,sizeof(last));memset(p,0,sizeof(p));len=0;
	for(int i=1;i<=m;i++) L[i].x=id[L[i].x],L[i].y=id[L[i].y];
	for(int i=1;i<=point;i++) siz[i+point]=siz[i];
	sort(L+1,L+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(L[i].x==L[i].y||(L[i-1].x==L[i].x&&L[i].y==L[i-1].y)) continue ;
		for(int j=0;j<=k;j++) ins(j*point+L[i].x,j*point+L[i].y);
		for(int j=0;j<k;j++) ins(j*point+L[i].y,(j+1)*point+L[i].x);
	}
	return ;
}
int spfa(int ST,int ED) 
{
	memset(dis,0,sizeof(dis));memset(v,true,sizeof(v));
	int st=1,ed=2;q[1]=ST;v[ST]=false;dis[ST]=0;
	while(st!=ed)
	{
		int x=q[st++];v[x]=true;//printf("%d ",x);
		for(int i=last[x];i!=-1;i=p[i].next)
		{
			int y=p[i].y;if(dis[y]>dis[x]+siz[y]) continue ;
			dis[y]=dis[x]+siz[y];if(v[y]) q[ed++]=y,v[y]=false;
		}
	} 
	return max(dis[ED],dis[ED+point]);
}
int main()
{
	memset(last,-1,sizeof(last));memset(v,false,sizeof(v));
	scanf("%d%d",&n,&m);k=1;
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		ins(x,y);L[i].x=x,L[i].y=y;
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfsx[i]) SH(i);
	}
	remake();
	if(point==1) printf("%d",siz[point]);
	else printf("%d",spfa(id[1],id[1]));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

cf的题Ehab and Path-etic MEXs口胡一下，不妨考虑考虑最差的情况如何取得。那么肯定是按照最小值取（也就是按着0，1，2）的顺序取。那么我们再考虑一下，我们只让它最多取到这三个数其中两个。那么就是最优解。（这题好像做过？）哦！注意一下链的情况。

#include
using namespace std;
int n,m,len=0,last[4000001],du[4000001],ans[4000001],maxx=0,cnt=0;
struct pp
{
	int x,y,next,num;
};pp p[4000001];
void ins(int x,int y,int num)
{
	int now=++len;
	p[now]={x,y,last[x],num};last[x]=now; 
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		du[x]++,du[y]++;ins(x,y,i);ins(y,x,i);
	}
	for(int i=1;i<=n;i++) maxx=max(maxx,du[i]);
	if(maxx<3) 
	{
		for(int i=1;i<=n-1;i++) printf("%d\n",i-1);
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(du[i]>=3)
		{
			for(int j=last[i];j!=-1;j=p[j].next) ans[p[j].num]=++cnt;
			break ;
		}
	} 
	for(int i=1;i<=n-1;i++) 
	{
		if(!ans[i]) ans[i]=++cnt;
	}
	for(int i=1;i<=n-1;i++) printf("%d\n",ans[i]-1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

这个板块太多了等下最后一道题Cow and Snacks，这一题最大的作用就是搞人心态，就像11 16的那道愚蠢的转移题。那么它将你的注意力吸引到了先后顺序（连通块上），但！真正的问题只需要用并查集。秒了具体想法写代码里。

//哼哼哼，误入歧途了吧~，考虑一下重合最多的情况是最优的（也就是第一个取走两个，第二三四五只拿一个）
//所以我们尝试直接维护连通块，若两个点不在同一个块里。合并并开心，要是在一个块里，不合并并不开心。（呜呜呜QWQ） 
//想想为什么？若是有先1 2,3 4,然后2 3是不是可能会出错？错！它可以先放2 3 进，再到1 2，3 4 。
//所以为什么可以这样维护呢，好吧说正事：若一个人喜欢x，y那么将其连边，然后一种合法的方案明显是一棵树感性画一下
//发现最优的解法就是树的的大小-1 ，所以...
//吃得少真的不会伤心嘛，我会的啊 
#include
using namespace std;
int n,m,fa[1000001],ans=0;
int findfa(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=findfa(fa[x]); 
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	while(m--)
	{
		int x,y;scanf("%d%d",&x,&y);
		int fx=findfa(x),fy=findfa(y);
		if(fx!=fy) fa[fx]=fy;
		else ans++;	
	}
	printf("%d",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28