P1841 JSOI2007 重要的城市

怎么还有这么水的蓝（

根据定义满足 dis(i,j)=dis(i,k)+dis(k,j)dis_{(i,j)}=dis_{(i,k)}+dis_{(k,j)} 并且有且只有一个 kk 就可以说是一个重要的城市

这个等于很好找，就是一个 O(n3)O(n^3) 的 floyd\text{floyd}

关键是这个有且只有一个的条件比较毒瘤，所以想到了计算最短路

其实我是xjb计算的，只需要满足我们这个式子算出来只有一条最短路的时候为 11 就行了

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=220;

int dis[maxn][maxn];
int f[maxn][maxn];
int e[maxn][maxn];
int bj[maxn];
int n,m;

int main()
{
	ios::sync_with_stdio(false);
	register int i,j,k;
	cin>>n>>m;
	int t1,t2,t3;
	//memset(e,0x3f,sizeof(e));
	memset(dis,0x3f,sizeof(dis));
	for(i=1;i<=m;i++)
	{
		cin>>t1>>t2>>t3;
		e[t1][t2]=t3;
		e[t2][t1]=t3;
		dis[t1][t2]=t3;
		dis[t2][t1]=t3;
	}
	for(i=1;i<=n;i++) dis[i][i]=0;
	for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	}
	for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		if(i==j||j==k||k==i) continue;
		if(dis[i][j]==dis[i][k]+dis[k][j]) f[i][j]++;
	}
//	for(k=1;k<=n;k++)
//	for(i=1;i<=n;i++)
//	for(j=1;j<=n;j++)
//	{
//		if(i==j||j==k||k==i) continue;
//		if(dis[i][j]==dis[i][k]+dis[k][j]) f[i][j]=f[i][k]*f[];
//	}
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	if(e[i][j]==dis[i][j]) f[i][j]++;
	int looker=0;
	for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		if(i==j||j==k||k==i) continue;
		if(f[i][j]==1&&dis[i][j]==dis[i][k]+dis[k][j]) bj[k]=1,looker=1;
	}
	if(!looker) 
	{
		cout<<"No important cities.\n"; 
		return 0;
	}
	for(i=1;i<=n;i++) if(bj[i]) cout<<i<<" ";
	cout<<endl; 
	return 0;
}

CF962F Simple Cycles Edges

大意就是找到图中所有简单环所在的边（相交的简单环不能贡献进入答案）

转化一下，如果一个环是简单环，那么一定是点数=边数

那么可以用 tarjan\text{tarjan} 求双连通分量，用两个 set\text{set} 来求点集和边集，然后在记录 BCC\text{BCC} 的时候看一下点集和边集大小是否相等即可

其实是树上差分过不了样例才打的这个

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
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cmath> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=200200;

int low[maxn],dfn[maxn],cnt,size=1,head[maxn];
int vis[maxn];
int n,m;

set <int> s1,s2;
stack <int> s;
vector <int> ans;

struct edge{
	int next,to;
}e[maxn];

inline void addedge(int next,int to)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

void tarjan(int t,int fat)
{
	dfn[t]=low[t]=++cnt;
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(vis[i]) continue;
		if(j==fat) continue;
		vis[i]=vis[i^1]=1;
		s.push(i);
		if(!dfn[j])
		{
			tarjan(j,t);
			low[t]=min(low[t],low[j]);
			if(low[j]>=dfn[t])
			{
			s1.clear(); s2.clear();
				s2.insert(t);
				while(s.top()!=i)
				{
					s1.insert(s.top()/2);
					s2.insert(e[s.top()].to);
					s.pop();
				}
				s1.insert(s.top()/2);
				s2.insert(e[s.top()].to);
				s.pop();
				if(s1.size()==s2.size())
				{
					set	<int>::iterator it;
					for(it=s1.begin();it!=s1.end();it++)
					{
						ans.push_back((*it));
					}
				}
			}
		}
		else low[t]=min(low[t],dfn[j]);
	}
	//cout<<t<<" "<<dfn[t]<<" "<<low[t]<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	ans.reserve(100000);
	register int i;
	cin>>n>>m;
	int t1,t2;
	for(int i=1;i<=m;i++)
	{
		cin>>t1>>t2;
		addedge(t1,t2);
		addedge(t2,t1);
	}
	for(i=1;i<=n;i++)
	{
		if(!dfn[i]) tarjan(i,i);
	}
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<endl;
	for(i=0;i<ans.size();i++) cout<<ans[i]<<" ";
	return 0;
}

P6005 [USACO20JAN]Time is Mooney G

差点做不出来一个绿题，看来美帝亡我之心不死啊

题面就是从 11 出发经过 tt 时间段后回到 11 获得的 wiw_i 总和减去 c∗time2c*time^2

这个暴力很好想，设f[i][j]f[i][j] 表示第jj 天在 ii 点能取得的最大收获

最后答案就是max⁡j=0n∗2f[1][j]−c∗j2\max\limits_{j=0}^{n*2}{f[1][j]-c*j^2}

看上去貌似没啥可以优化的，我们考虑一下后面那个 j2j^2 有什么用

我们不好找到最长的环的长度，因此我们设整个环的长度为 wsumw_{sum} ，显然，当 jj 在 2∗wsumc\sqrt{\frac{2*w_{sum}}{c}} 的时候，每次多 1s1s 的时候答案无论如何都会减小了，无论 wiw_i 如何，尽快跑回 11 号点才是最优的

无论的时际运行要快7070% (1.05s→276ms1.05s\to 276ms)

然后就可以在 O(n∗2∗wsumc)O(n*\sqrt{\frac{2*w_{sum}}{c}}) 时间复杂度内解决这题。

然后发现正常写法100多ms我直接暴毙

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=1020;

int n,m,head[maxn],size,wsum;
int f[maxn][maxn];
int target;
int a[maxn];

struct edge{
	int next,to;
}e[maxn*2];

inline void addedge(int next,int to)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

int vis[maxn][maxn],ans;
int v[maxn];

void bfs()
{
	int looker=sqrt(wsum/target)+1;
	queue <pair<int,int> > q;
	q.push(make_pair(1,0));
	while(!q.empty())
	{
		int t=q.front().first;
		int tm=q.front().second;
		if(t==1&&ans<f[t][tm]-target*tm*tm) ans=f[t][tm]-target*tm*tm;
		q.pop();
		int i,j,k;
		if(tm+1<=looker)
		{
			for(i=head[t];i;i=e[i].next)
			{
				j=e[i].to;
				k=a[j];
				f[j][tm+1]=max(f[j][tm+1],f[t][tm]+k);
				if(!vis[j][tm+1]) vis[j][tm+1]=1,q.push(make_pair(j,tm+1));
			}
		}
		else
		{
			for(i=head[t];i;i=e[i].next)
			{
				j=e[i].to;
				k=a[j];
				f[j][tm+1]=max(f[j][tm+1],f[t][tm]+k);
				if(!v[j]) v[j]=1,q.push(make_pair(j,tm+1));
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m>>target;
	int t1,t2,t3;
	for(i=1;i<=n;i++) cin>>a[i],wsum+=a[i];
	for(i=1;i<=m;i++)
	{
		cin>>t1>>t2;
		addedge(t1,t2);
	}
	bfs();
	cout<<ans<<endl;
	return 0;
}

P4208 [JSOI2008]最小生成树计数

首先一个性质是最小生成树中边权相等的边数量一定相等，并且当连接了权值为 vv 以下的边后连通性一定相等

首先考虑连通性，我们是对每个点贪心然后能用则用，因此连通性一定相等。

然后考虑权值相同的边一定相等，我们当前构造出的最优的生成树有 kk 个权值为 vv 的边，如果某个最小生成树包含少于 kk 个权值为 vv 的边，因为是一样的连通性，因此这个最小生成树总权值更小，我们构造的就不是最小的生成树

最后特判一下能不能构成最小生成树就行了

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
89
90
91
92
93
94
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1100;
const int modp=31011;

int n,m,cnt[maxn],f[maxn],loooker[maxn];
int ssz;
int tmp[maxn],ans=1;
int l[maxn];

struct edge{
	int x,y,val;
	bool operator <(const edge &b)
	const {
		return val<b.val;
	}
}e[maxn];

int getfather(int x,int *f)
{
	if(x==f[x]) return x;
	return f[x]=getfather(f[x],f);
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j,k;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>e[i].x>>e[i].y>>e[i].val;
	}
	for(i=1;i<=n;i++) f[i]=i,loooker[i]=i; 
	sort(e+1,e+m+1);
	int looker,las=0,cnt=0,tmpans;
	for(i=1;i<=1024;i++) l[i]=l[i>>1]+(i&1);
	for(i=1;i<=m;i++)
	{
		looker=0;
		if(e[i].val!=e[i+1].val) looker=1;
		int xx,yy;
		xx=getfather(e[i].x,f);
		yy=getfather(e[i].y,f);
		if(xx!=yy) f[yy]=xx,cnt++,ssz++;
		if(looker)
		{
			int sz=i-las;
			tmpans=0;
			for(j=0;j<=(1<<sz)-1;j++)
			{
				if(l[j]!=cnt) continue;
				memcpy(tmp,loooker,(sizeof(int)*(n+5)));
				for(k=1;k<=sz;k++)
				{
					if(j&(1<<(k-1)))
					{
						k+=las;
						int xx,yy;
						xx=getfather(e[k].x,tmp);
						yy=getfather(e[k].y,tmp);
						if(xx==yy)
						{
							tmpans--;
							break;
						}
						tmp[yy]=xx;
						k-=las;
					}
				}
				tmpans++;
			}
			ans=(ans*tmpans)%modp; 
			cnt=0;
			looker=0;
			las=i;
			memcpy(loooker,f,sizeof(int)*(n+5));
		}
	}
	cout<<(ssz==n-1?ans:0)<<endl;
	return 0;
}

P5994 [PA2014] Kuglarz

考虑 [l,r][l,r] 奇偶性意义

[l,l][l,l] 的奇偶性可以由 [l,r],[l+1,r][l,r],[l+1,r] 求出

或者说，我们知道了[x,y],[y,b][x,y],[y,b] 的奇偶性，那么可以得到[x,b][x,b] 的奇偶性

这东西转化到图上就是每个点都联通

然后完了吗，完了。

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=2020;

vector <int> v;

int dis[maxn][maxn];
int n,m;
int f[maxn];
int tot;
long long ans=0;
//int val[maxn],ans=0;

struct edge{
	int x,y,val;
	bool operator <(const edge &b)
	const {
		return val<b.val;
	}
}e[maxn*maxn];

int getfather(int x)
{
	if(x==f[x]) return x;
	return f[x]=getfather(f[x]);
}

void kru()
{
	int i,j,p=0;
	for(i=1;i<=tot;i++)
	{
		if(p==n) break;
		int x,y;
		x=e[i].x,y=e[i].y;
		x=getfather(x);
		y=getfather(y);
		if(x==y) continue;
		f[y]=x;
		p++;
		//cout<<e[i].x<<" "<<e[i].y-1<<endl;
		ans+=e[i].val;
	}
	return ;
}

int main()
{
	//ios::sync_with_stdio(false);
	register int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		f[i]=i;
		for(j=i;j<=n;j++)
		{
			tot++;
			scanf("%d",&e[tot].val); e[tot].y=j+1,e[tot].x=i; 
			//cin>>dis[i-1][j],ans+=v[i];
			//if(i==j) val[i]=dis[i-1][j];
			//dis[j][i-1]=dis[i-1][j];
		}
	}
	f[n+1]=n+1;
	sort(e+1,e+tot+1);
	kru();
	printf("%lld",ans);
	//v.reserve(4000);
	return 0;
}

变式：如果球只有一个
目前能想到的就是利用很多vector 然后每次插入两个堆里面跑最小生成树，（其实需要zkw线段树这种比较稳），然后 O(n3α(n))O(n^3\alpha(n)) 可以做？

CF437D The Child and Zoo

令 fi,jf_{i,j} 为 ii 到 jj 的所有路径上的最小值的最大值

然后求 $\large\frac{\sum\limits_{\forall i\neq j}f_{i,j}}{n*(n-1)} $

考虑哪些点会贡献答案

首先给个结论：如果这张图本身是联通的，那么这些路径合在一起一定可以变成一棵树

证明：如果不是树就出现了环，我们找到这个环上面最小值（我们一定会想办法不经过，就把这个环拆开，把最小值看做叶子节点即可，对答案无影响）

因此我们建立最大生成树，然后对每个割边来统计一下答案，一定要注意比较大小的函数不能写等于（不然大点会RE）

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=200100;

int n,m,val[maxn],f[maxn],sz[maxn];
long long ans=0;

struct edge{
	int x,y; 
	bool operator <(const edge &b)
	const {
		return min(val[x],val[y])>min(val[b.x],val[b.y]);
	}
}e[maxn];

int getfather(int x)
{
	if(x==f[x]) return x;
	return f[x]=getfather(f[x]);
}

inline void kru()
{
	int i,p=0;
	for(i=1;i<=m;i++)
	{
		if(p==n-1) break;
		int x,y;
		x=e[i].x;
		y=e[i].y;
		int looker=min(val[x],val[y]);
		x=getfather(x);
		y=getfather(y);
		if(x==y) continue;
		p++;
		if(sz[x]<sz[y]) swap(x,y);
		f[y]=x;
		ans+=2ll*sz[x]*sz[y]*looker;
		sz[x]+=sz[y]; 
	}
	return ;
}

int main()
{
	//ios::sync_with_stdio(false);
	register int i;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d",&val[i]),f[i]=i,sz[i]=1;
	for(i=1;i<=m;i++) scanf("%d %d",&e[i].x,&e[i].y);
	sort(e+1,e+m+1);
	kru();
	printf("%.5lf",double(double(ans)/double(1ll*n*(n-1))));
	return 0;
}

P6192 【模板】最小斯坦纳树

就是给你关键点让你找包含这些关键点的生成树权值的最小值

这种问题关键点点集都很小（ ≈10\approx10 ,再大些你可以拿图灵奖了）

我们利用动态规划设 f[i][S]f[i][S] 表示以ii 为根并且关键点连通性为 SS 的最花费，对于转移有以下几个

1.从子树转移 f[i][S]=f[j][S]+val(i,j)f[i][S]=f[j][S]+val_{(i,j)}

2.从自己转移 f[i][S]=min⁡s1⊕s2=n(f[i][s1]+f[i][s2],f[i][S])f[i][S]=\min\limits_{s1\oplus s2=n}(f[i][s1]+f[i][s2],f[i][S])

我们已经处理完了s1,s2s1,s2 这两个子集，那么我们先处理完 22 转移，剩下的就相当于一个松弛操作，用 dijkstra\text{dijkstra} 处理就行了，因为我们无需考虑整张图的方向，只需要知道子树里面有这个点集 SS 就行了

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
89
90
91
92
93
94
95
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=120;

struct edge{
	int next,to,dis;
}e[2020];

int f[120][1025];
int head[maxn],vis[maxn],size;
int n,m,target;
int l[maxn],p[maxn];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].next=head[next];
	e[size].dis=dis;
	head[next]=size;
}

priority_queue <pair<int,int> > q; 

inline void dij(int state)
{
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	{
		int t=q.top().second;
		q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		int i,j,k;
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			k=e[i].dis;
			if(f[t][state]+k<f[j][state])
			{
				f[j][state]=f[t][state]+k;
				q.push(make_pair(-f[j][state],j));
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	int i,j,k;
	cin>>n>>m>>target;
	int t1,t2,t3;
	for(i=1;i<=m;i++)
	{
		cin>>t1>>t2>>t3;
		addedge(t1,t2,t3);
		addedge(t2,t1,t3);
	}
	for(i=1;i<=target;i++)
	{
		cin>>p[i];
		l[p[i]]=1<<(i-1);
	}
	memset(f,0x3f,sizeof(f));
	for(i=1;i<=target;i++)
	{
		f[p[i]][l[p[i]]]=0;
	}
	for(i=0;i<=(1<<target)-1;i++)
	{
		for(j=1;j<=n;j++)
		{
			for(k=i;k;k=(k-1)&i)
			{
				f[j][i]=min(f[j][k]+f[j][i^k],f[j][i]);
			}
			if(f[j][i]!=f[0][0]) q.push(make_pair(-f[j][i],j));
		}
		dij(i);
	}
	cout<<f[p[1]][(1<<target)-1]<<endl;
	return 0;
}

P4294 [WC2008]游览计划

神！tommy\color{black}{t}\color{red}{ommy} 神！

这个是一个最小斯坦纳树的题目，照着模板我们状压即可

考虑回溯，同层的我们记录前驱，不同层暴力枚举然后 dfs 找就行了

然后注意一下细节，这个题的权是点权而不是边权，因此每次子树合并的时候要减去自己

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=110;

int n,m,target;
int f[maxn][1025],pre[maxn][1025];
int head[maxn],num[11][11];
int chk[12][12];
int size,vis[maxn];
int p[maxn],cnt;
int nx[maxn],ny[maxn];
int val[maxn];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int bj[maxn];

priority_queue <pair<int,int> > q;

struct edge{
	int next,to,dis;
}e[maxn*maxn*3];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

inline void dij(int state)
{
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	{
		int t=q.top().second;
		q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		int i,j,k;
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			k=e[i].dis;
			if(f[t][state]+k<f[j][state])
			{
				f[j][state]=f[t][state]+k;
				pre[j][state]=t;
				q.push(make_pair(-f[j][state],j));
			}
		}
	}
}

void dfs(int t,int s)
{
	while(pre[t][s]!=-1) bj[t]=1,t=pre[t][s];
	for(int i=s;i;i=(i-1)&s)
	{
		if(f[t][s]==f[t][i]+f[t][s^i]-val[t])
		{
			dfs(t,i);
			dfs(t,s^i);
			return ;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j,k;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		num[i][j]=(i-1)*m+j;
		cin>>val[num[i][j]];
		nx[num[i][j]]=i;
		ny[num[i][j]]=j;
		chk[i][j]=1;
		if(val[num[i][j]]==0) p[++target]=num[i][j];
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	for(k=0;k<=3;k++)
	{
		if(!chk[i+dx[k]][j+dy[k]]) continue;
		addedge(num[i][j],num[i+dx[k]][j+dy[k]],val[num[i+dx[k]][j+dy[k]]]);
	}
	memset(f,0x3f,sizeof(f));
	memset(pre,-1,sizeof(pre));
	for(i=1;i<=target;i++) f[p[i]][1<<(i-1)]=0;
	int s=0;
	for(s=0;s<=(1<<target)-1;s++)
	{
		for(i=1;i<=n*m;i++)
		{
			for(j=s;j;j=(j-1)&s) f[i][s]=min(f[i][s],f[i][j]+f[i][s^j]-val[i]);
			if(f[i][s]!=f[0][0]) 
			q.push(make_pair(-f[i][s],i));
		}
		dij(s);
	}
	dfs(p[1],(1<<target)-1);
	cout<<f[p[1]][(1<<target)-1]<<endl;
	for(i=1;i<=n;i++,cout<<endl)
	for(j=1;j<=m;j++)
	{
		if(val[num[i][j]]==0) cout<<'x';
		else if(bj[num[i][j]]) cout<<'o';
		else cout<<'_';
	}
	return 0;
}

P3403 跳楼机

每次有三种个操作：

1.向上移动 x,yx,y 或 zz

2.回到 11

显然 2 操作可以被看成是取模，我们设 f[i]f[i] 为模 xx 意义下高度为 ii 的点能用向上走 y,zy,z 到的最低的点，显然我们有转移方程

f[(i+y)(modx)]=f[i]+yf[(i+y)\pmod x ]=f[i]+y

f[(i+z)(modx)]=f[i]+zf[(i+z)\pmod x ]=f[i]+z

这个转移实际上并没有公式这样好描述，因此我们用图来转移

最后仅考虑1操作,对每个模意义下的高度,ans+=(h−f[i])/x+1ans+=(h-f[i])/x+1（这个很显然）

还要转移从 11 开始，f[0]f[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
89
90
91
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=100100;

int head[maxn],size,n;
int dis[maxn];
int vis[maxn];

struct edge{
	int next,to,dis;
}e[maxn*2];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

inline void dij()
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	priority_queue <pair<int,int > > q;
	q.push(make_pair(1,1));
	dis[1]=1;
	while(!q.empty())
	{
		int t=q.top().second;
		int i,j,k;
		q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			k=e[i].dis;
			if(dis[t]+k<dis[j])
			{
				dis[j]=dis[t]+k;
				q.push(make_pair(-dis[j],j)); 
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n;
	int a,b,c;
	cin>>a>>b>>c;
	if(a==1||b==1||c==1) 
	{
		cout<<n<<endl;
		return 0;
	}
	if(a>b) swap(a,b);
	if(a>c) swap(a,c);
	for(i=0;i<a;i++)
	{
		addedge(i,(i+b)%a,b);
		addedge(i,(i+c)%a,c);
	}
	dij();
	int ans=0;
	for(i=0;i<a;i++)
	{
		if(dis[i]<=n)
		ans+=(n-dis[i])/a+1;
	}
	cout<<ans<<endl;
	return 0;
}


P2371 [国家集训队]墨墨的等式

把上面这题的思想搞懂了就很好做

不过我是先开的这个然后被教育了才先做的上面那个

首先我们建模，把 nn 个点拆成 $\sum a*n $ 个点，向下的边权为 a[i]a[i] 向右的边权为0实际上我们不需要考虑连通性，所以我们先不管向右的，最后点的路径在 [L,R][L,R] 之间的就是答案

换句话说，如果 R−LR-L 小于某个值，我将绝杀，可惜换不得

我们参照上面那题的思路，做一个在模某个数意义下的最短路，显然应该选最小的，因为这样最快（实测能快2s2s ）

此外还需要注意的是，本题是从 00 开始

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
89
90
91
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=500500;

int n,m,head[maxn],dis[maxn],r,l;
int vis[maxn],size;
int a[maxn];

struct dedge{
	int next,to,dis;
}e[maxn*13];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

inline void dij()
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	priority_queue <pair<int,int> > q;
	q.push(make_pair(0,0));
	dis[0]=0;
	//for(int i=2;i<=n;i++) dis[a[i]%a[1]]=min(dis[a[i]%a[1]],a[i]),q.push(make_pair(-dis[a[i]%a[1]],a[i]%a[1]));
	while(!q.empty())
	{
		int t=q.top().second;
		q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		int i,j,k;
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			k=e[i].dis;
			if(dis[t]+k<dis[j]) 
			{
				dis[j]=dis[t]+k;
				q.push(make_pair(-dis[j],j));
			}
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>l>>r;
	for(i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(i=0;i<=a[1];i++)
	{
		for(j=2;j<=n;j++)
		{
			addedge(i,(i+a[j])%a[1],a[j]);
		}
	}
	dij();
	int ans=0;
	l--;
	for(i=0;i<=a[1];i++)
	{
		if(dis[i]>r) continue;
		int aa,bb;
		aa=(r-dis[i])/a[1]+1;
		if(dis[i]>l) bb=0;
		else bb=(l-dis[i])/a[1]+1;
		ans+=(aa-bb);
	}
	cout<<ans<<endl;
	return 0;
}

P2783 有机化学之神偶尔会做作弊

首先环一定是一个边双，其次环长度一定要大于3（题面定义）

因此求边双就不能考虑父亲的情况

然后基本就是套路了

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1e5+10;

int head[maxn],dfn[maxn],low[maxn],bcc[maxn];
int size,n,sz[maxn],dt,m;
int ins[maxn];
int cnt;
int f[maxn],id[maxn],top[maxn],dep[maxn],son[maxn];

stack <int> s;
map <pair<int,int>,bool> mp;

struct edge{
	int next,to;
}e[maxn<<1],looker[maxn<<1];

inline void addedge(int next,int to)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

void tarjan(int t,int fat)
{
	int visfat=0;
	dfn[t]=low[t]=++dt;
	s.push(t); ins[t]=1;
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		//if(j==fat&&!visfat) {visfat=1; continue;}
		if(j==fat) continue;
		if(!dfn[j])
		{
			tarjan(j,t);
			low[t]=min(low[j],low[t]);
		}
		else if(ins[j])
		{
			low[t]=min(dfn[j],low[t]);
		}
	}
	j=0;
	int tmpsz=0;
	if(low[t]==dfn[t])
	{
		cnt++;
		tmpsz=0;
		while(j!=t)
		{
			tmpsz++;
			j=s.top();
			s.pop();
			ins[j]=0;
			bcc[j]=cnt;
		}
		sz[cnt]=tmpsz;
	}
}

void dfs1(int t,int fat)
{
	int i,j;
	dep[t]=dep[fat]+1;
	f[t]=fat;
	sz[t]=1;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==fat) continue;
		dfs1(j,t);
		sz[t]+=sz[j];
		if(sz[j]>sz[son[t]]) son[t]=j;
	}
}

void dfs2(int t,int topt)
{
	int i,j;
	id[t]=++cnt;
	top[t]=topt;
	if(!son[t]) return ;
	dfs2(son[t],topt);
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==f[t]||j==son[t]) continue;
		dfs2(j,j);
	}
}

int getans(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=dep[x]-dep[top[x]]+1;
		x=f[top[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	ans+=dep[x]-dep[y]+1;
	return ans;
}

inline void getnewmap()
{
	int i,j;
	memset(head,0,sizeof(head));
	size=0;
	for(i=1;i<=m;i++)
	{
		int tx=bcc[looker[i].next];
		int ty=bcc[looker[i].to];
		if(tx>ty) swap(tx,ty);
		if(tx==ty) continue;
		if(mp[make_pair(tx,ty)]) continue;
		mp[make_pair(tx,ty)]=1;
		addedge(tx,ty);
		addedge(ty,tx);
	}
	memset(sz,0,sizeof(sz));
	cnt=0;
	dfs1(1,1);
	dfs2(1,1);
}

inline void prit(int x)
{
	stack <int> s;
	int j=1;
	while(x)
	{
		if(x&j) x-=j,s.push(1);
		else s.push(0);
		j<<=1;
	}
	while(!s.empty()) printf("%d",s.top()),s.pop();
	printf("\n");
	//cout<<endl;
}

int main()
{
	//ios::sync_with_stdio(false);
	register int i,j;
	scanf("%d %d",&n,&m);
	int t1,t2;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&t1,&t2);
		looker[i].to=t2;
		looker[i].next=t1;
		addedge(t1,t2);
		addedge(t2,t1);
	}
	for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
	getnewmap();
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&t1,&t2);
		//cin>>t1>>t2;
		t1=bcc[t1];
		t2=bcc[t2];
		//cout<<getans(t1,t2)<<endl;
		prit(getans(t1,t2));
	}
	return 0;
}

SP2878 KNIGHTS - Knights of the Round Table

刚开始想的是暴力建图用 dinicdinic 跑网络流，然后发现点不会处理，想到在 KnK_n 上面删边然后找奇环，看起来这做法似乎没问题了，然而统计答案的时候太麻烦了，才知道可以在每一个点双连通分量里面统计答案（果然是我太菜了）

做法应该能想出80%,只是没去学求点双想不到最后20%

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxm=1e6+10;
const int maxn=1e3+10;

int looker[maxn][maxn];
int n,m,head[maxn],size,col[maxn];
int dfn[maxn],low[maxn],ins[maxn],dt,cnt;
int lker[maxn];
int bj,ans,vis[maxn];
//int col[maxn];

stack <int> s;
vector <int> bcc[maxn];

struct edge{
	int next,to;
}e[maxm<<1];

inline void addedge(int next,int to)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

void tarjan(int t,int fat)
{
	dfn[t]=low[t]=++dt;
	ins[t]=1;
	s.push(t);
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(j==fat) continue;
		if(!dfn[j])
		{
			tarjan(j,t);
			low[t]=min(low[j],low[t]);
			if(low[j]>=dfn[t])
			{
				int k=0;
				cnt++;
				while(k!=j)
				{
					k=s.top();
					s.pop();
					ins[k]=0;
					bcc[cnt].push_back(k);
				}
				//bcc[cnt].push_back(j);
				bcc[cnt].push_back(t);
			}
		}
		else if(ins[j]) low[t]=min(dfn[j],low[t]);
	}	
}

void check(int t,int fat)
{
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		//j==fat||
		if(lker[j]!=cnt) continue;
		if(col[j]!=-1&&col[j]==col[t]) 
		{
			bj=1;
			return ;
		}
		if(col[j]==-1) col[j]=col[t]^1,check(j,t);
		//if(col[j]==col[t]) bj=0;
	}
}

inline void solve()
{
	register int i,j;
	int t1,t2;
	memset(looker,0,sizeof(looker));
	memset(head,0,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(vis,0,sizeof(vis));
	memset(ins,0,sizeof(ins));
	memset(col,0,sizeof(col));
	memset(lker,0,sizeof(lker));
	while(!s.empty()) s.pop();
	cnt=dt=size=ans=0;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&t1,&t2);
		looker[t1][t2]=1;
		looker[t2][t1]=1;
	}
	//scanf("%d %d",&t1,&t2);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		if(i==j) continue;
		if(!looker[i][j]) addedge(i,j);
	}
	for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
	//for(i=1;i<=cnt;i++,cout<<endl)
	//for(j=0;j<bcc[i].size();j++) cout<<bcc[i][j]<<" ";
	while(cnt)
	{
		bj=0;
		int sz=bcc[cnt].size(); 
		if(sz<=2)
		{
			bcc[cnt].clear();
			cnt--;
			continue;
		}
		for(i=0;i<bcc[cnt].size();i++) lker[bcc[cnt][i]]=cnt,col[bcc[cnt][i]]=-1; 
		col[bcc[cnt][0]]=1;
		check(bcc[cnt][0],bcc[cnt][0]);
		if(bj)
		{
			for(i=0;i<bcc[cnt].size();i++) vis[bcc[cnt][i]]=1;
		}
		bcc[cnt].clear();
		cnt--;
	}
	for(i=1;i<=n;i++) if(!vis[i]) ans++;
	printf("%d\n",ans);
	return ;
}

int main()
{
	while(scanf("%d %d",&n,&m))
	{
		if(n==0&&m==0) return 0;
		solve();
	}
}

P3119 [USACO15JAN]Grass Cownoisseur G

大意就是求当图中一条边变成双向边能包含1的强连通块的个数

推一上午分层图没搞懂，于是去写了一个两遍最短路的

首先第一次从得到从 11 开始的最长路，然后建立反图得到每个点到1的最长路

然后就是拼路径了，注意的是两个不连通的路径才能拼在一起

正确性显然（如果拼在一起如果重合了说明原图存在环）

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=200100;

int d1[maxn],d2[maxn]; 
int n,m,head[maxn],sz[maxn],cnt,bl[maxn];
int dfn[maxn],low[maxn],dt,vis[maxn],size,ins[maxn];
int ans=0;

stack <int> s;
map <pair<int,int>,int> mp;

struct edge{
	int next,to,dis,bh;
}e[maxn<<1],looker[maxn<<1];

//inline int f(int x)
//{
//	return x+n;
//}

inline void addedge(int next,int to,int dis=0,int bh=0)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].bh=bh;
	e[size].next=head[next];
	head[next]=size;
	
}

void tarjan(int t)
{
	low[t]=dfn[t]=++dt;
	s.push(t);
	ins[t]=1;
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(!dfn[j]) tarjan(j),low[t]=min(low[t],low[j]);
		else if(ins[j]) low[t]=min(low[t],dfn[j]);
	}
	j=0;
	if(dfn[t]==low[t])
	{
		cnt++;
		while(j!=t)
		{
			j=s.top();
			s.pop();
			ins[j]=0;
			bl[j]=cnt;
			sz[cnt]++;
		}
	}
}

inline void spfa(int st,int finger,int *dis)
{
	int i,j;
	queue <int> q;
	memset(vis,0,sizeof(vis));
	memset(dis,-1,sizeof(dis));
	q.push(st);
	dis[st]=sz[st];
	while(!q.empty())
	{
		int t=q.front();
		vis[t]=0; q.pop();
		int i,j,k,f;
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			k=e[i].dis;
			f=e[i].bh;
			if(f!=finger) continue;
			if(dis[t]+k>dis[j])
			{
				dis[j]=dis[t]+k;
				if(vis[j]) continue;
				vis[j]=1; q.push(j);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	int t1,t2;
	for(i=1;i<=m;i++) cin>>t1>>t2,addedge(t1,t2),looker[i].next=t1,looker[i].to=t2;
	for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	memset(head,0,sizeof(head)); size=0;
	for(i=1;i<=m;i++)
	{
		t1=looker[i].next;
		t2=looker[i].to;
		t1=bl[t1],t2=bl[t2];
		if(t1==t2) continue;
		if(mp[make_pair(t1,t2)]) continue;
		addedge(t1,t2,sz[t2],1);
		addedge(t2,t1,sz[t1],2);
		mp[make_pair(t1,t2)]=1;
	}
	//for(i=1;i<=cnt;i++) addedge(cnt+1,i,0,2);
	spfa(bl[1],1,d1);
	spfa(bl[1],2,d2);
	ans=sz[bl[1]];
	for(i=1;i<=cnt;i++)
	{
		if(!d1[i]) continue;
		for(j=head[i];j;j=e[j].next)
		{
			int k,l;
			k=e[j].to; l=e[j].bh;
			if(l!=2||!d2[k]) continue;
			ans=max(ans,d1[i]+d2[k]-sz[bl[1]]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

UVA1146 Now or later

有 mm 架飞机每个飞机可以选择早着陆和玩着陆，询问着陆时间的差值的最小的最大值

首先 $ t\leq10^7$ 表示这多半是个二分，我们考虑二分的答案 tt

现在要判断 tt 是否合法，一种可行的办法是用 2-SAT\text{2-SAT}

将一个点拆分成早到和晚到两个点，出现在一个 scc\text{scc} 的意义就是无论早到和晚到都不合法，考虑连边，可以写成下面这个表格

下边为i右边为j 早到 晚到
早到 (f(i)=i+n) i->f(j) i->j
晚到 f(i)->f(j) f(i)->j

只用不合法的情况是 i,ji,j 无论早到晚到都会低于最小值，此时会连

(i,f(j)),f(i,j),(i,j),(j,i),(f(j),f(i))(i,f(j)),f(i,j),(i,j),(j,i),(f(j),f(i)) 等边，i,j,f(i),f(j)i,j,f(i),f(j) 在一个 scc\text{scc} 里面

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=5e3+20;
const int maxm=2e7+20;

struct edge{
	int next,to;
}e[maxm];

struct que{
	int a,b;
	bool operator <(const que &tmp)
	const {
		if(a==tmp.a) return b<tmp.b;
		return a<tmp.a; 
	}
}q[maxn];

int ins[maxn],head[maxn],size,dfn[maxn],low[maxn],bl[maxn],sz[maxn];
int n,m;
int a[maxn],b[maxn],timmx,col,dt;

stack <int> s;

inline int f(int x)
{
	return x+n;
}

inline void addedge(int next,int to)
{
	e[++size].to=to;
	e[size].next=head[next];
	head[next]=size;
}

void tarjan(int t)
{
	dfn[t]=low[t]=++dt;
	s.push(t); ins[t]=1;
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(!dfn[j])
		{
			tarjan(j); low[t]=min(low[j],low[t]);
		}
		else if(ins[j]) low[t]=min(low[t],dfn[j]);
	}
	j=0;
	if(dfn[t]==low[t])
	{
		++col;
		while(j!=t)
		{
			j=s.top();
			s.pop();
			ins[j]=0;
			bl[j]=col;
		}
	}
}

inline int check(int x)
{
	int i,j;
	memset(head,0,sizeof(head)); size=0;
	memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low));
	dt=0; while(!s.empty()) s.pop(); memset(ins,0,sizeof(ins));
	col=0; memset(bl,0,sizeof(bl));
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		if(i==j) continue;
		if(abs(a[i]-a[j])<x) addedge(i,f(j));//addedge(f(j),i);
		if(abs(a[i]-b[j])<x) addedge(i,j);//addedge(j,i);
		if(abs(b[i]-a[j])<x) addedge(f(i),f(j));//addedge(f(j),f(i));
		if(abs(b[i]-b[j])<x) addedge(f(i),j);//addedge(j,f(i));
	}
	for(i=1;i<=n+n;i++) if(!dfn[i]) tarjan(i);
	for(i=1;i<=n;i++) if(bl[i]==bl[f(i)]) return 0;
	return 1;
}

inline int getans()
{
	int l=1,r=timmx;
	int mid,ans=0;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1; 
	}
	return ans;
}

inline void solve()
{
	int i,j;
	timmx=0;
	for(i=1;i<=n;i++) cin>>a[i]>>b[i],timmx=max(timmx,max(a[i],b[i]));
	cout<<getans()<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	while(cin>>n) solve();
	//for(i=1;i<=n;i++) cin>>q[i].a>>q[i].b,if(q[i].a>q[i].b) swap(q[i].a,q[i].b);
	//sort(q+1,q+m+1) timmx=q[n].b;
	return 0;
}

UVA11478 Halum

怪毙了的差分约束

首先我们设未知数为每个点的操作次数，此时即可以得到xi−xj+dis=kx_i-x_j+dis=k 即此时的边权最小值为 kk，二分k不出现负环即可

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=100100;

int n,m,head[maxn],dis[maxn],size,vis[maxn];
int vis_sum[maxn],delta,f;

struct edge{
	int next,to,dis;
}e[maxn<<1];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

void dfs(int t)
{
	vis_sum[t]=1;
	vis[t]=1;
	if(f) return ;
	int i,j,k;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		k=e[i].dis-delta;
		if(dis[t]+k<dis[j])
		{
			dis[j]=dis[t]+k;
			if(vis[j])
			{
				f=1;
				return ;
			}
			dfs(j);
		}
	}	
	vis[t]=0;
}

inline int check(int x)
{
	delta=x;
	memset(vis_sum,0,sizeof(vis_sum));
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	f=0;
	for(int i=1;i<=n;i++)
	if(!vis_sum[i]) dis[i]=0,dfs(i);
	if(f) return 0;
	else return 1;
	
}

inline int solve()
{
	int i,j,t1,t2,t3;
	for(i=1;i<=m;i++) cin>>t1>>t2>>t3,addedge(t1,t2,t3);
	int l=1,r=1e4+1,mid,ans=0;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	if(ans>=(int)1e4+1) cout<<"Infinite\n";
	else if(!ans) cout<<"No Solution\n";
	else cout<<ans<<"\n";
	return 0;
}

inline void memclr()
{
	memset(head,0,sizeof(head));
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(vis_sum,0,sizeof(vis_sum));
	size=0;
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	while(cin>>n>>m)
	{
		memclr();
		solve();
	}
	return 0;
}

P4366 [Code+#4]最短路

怪毙了这居然还能紫。

考虑实际意义，最短路即为把 AA 替换成 BB 的最短代价

用二进制来分析，整个替换相当于每次把一位上的数异或 11

于是建图，每个点连二进制下 11 的个数和自己相差 11 的点，代价为异或和乘 CC

唯一的锅貌似就是 maxm\text{maxm} 写成了 maxn\text{maxn}

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
89
90
91
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=530500;
const int maxm=maxn*10;

int n,m,head[maxn],dis[maxn],c,lmt=1;
int vis[maxn],size;
int st,ed;

struct edge{
	int next,to,dis;
}e[maxm<<1];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}

inline void _mcolor(int x)
{
	int i,target;
	for(i=1;i<=lmt;i*=2)
	{
		target=x^i;
		if(target<=x) continue;
		addedge(x,target,c*(x^target));
		addedge(target,x,c*(x^target));
	}
}

inline void dij(int st)
{
	priority_queue < pair<int,int> > q;
	q.push(make_pair(0,st));
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[st]=0;
	while(!q.empty())
	{
		int t=q.top().second;
		q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		int i,j,k;
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			k=e[i].dis;
			if(dis[t]+k<dis[j])
			{
				dis[j]=dis[t]+k;
				q.push(make_pair(-dis[j],j));
			}
		}
	}
	return ;
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m>>c;
	while(lmt<=n) lmt*=2;
	for(i=0;i<=lmt;i++) _mcolor(i);
	int t1,t2,t3;
	for(i=1;i<=m;i++) 
	{
		cin>>t1>>t2>>t3;
		addedge(t1,t2,t3);
	}
	cin>>st>>ed;
	dij(st);
	cout<<dis[ed]<<endl;
	return 0; 
}

P3831 [SHOI2012]回家的路

又是一个大水题，考虑建图

在同一排同一列的，可以直接从小到大连边。

由于有换乘的费用，不如将每个点裂成两个点，此时横向的点编号为 ii ，纵向的点编号为 f(i)=i+mf(i)=i+m 连一条i,i+mi,i+m 费用为 11 的边表示换乘费用。

注意起点按照样例来说应该是不用换乘，实现起来很简单

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=400200;

int n,m,head[maxn],size,dis[maxn],vis[maxn];

struct edge{
	int next,to,dis;
}e[maxn<<1];

inline void addedge(int next,int to,int dis)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].next=head[next];
	head[next]=size;
}


inline int f(int x)
{
	return x+m;
}

struct node{
	int x,y,bh;
}a[maxn];

int rowcmp(node a,node b)
{
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

int colcmp(node a,node b) 
{
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}

inline void dij(int st)
{
	priority_queue <pair<int,int> > q;
	q.push(make_pair(0,st));
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[st]=0;
	dis[f(st)]=0;
	q.push(make_pair(0,f(st)));
	while(!q.empty())
	{
		int t=q.top().second;
		q.pop(); 
		if(vis[t]) continue;
		vis[t]=1;
		int i,j,k;
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			k=e[i].dis;
			if(dis[t]+k<dis[j])
			{
				dis[j]=dis[t]+k;
				q.push(make_pair(-dis[j],j));
			}
		}
	}
}

int lasi=0;

inline void rowadd(int x)
{
	if(a[lasi+1].x!=x) return ;
	lasi++;
	for(int i=lasi;i<=m;i++)
	{
		if(a[i+1].x!=x) return ;
		addedge(f(a[i].bh),f(a[i+1].bh),(a[i+1].y-a[i].y)*2);
		addedge(f(a[i+1].bh),f(a[i].bh),(a[i+1].y-a[i].y)*2);
		//cout<<f(a[i].bh)<<" "<<f(a[i+1].bh)<<endl;
		//cout<<a[i].x<<" "<<a[i].y<<" "<<a[i+1].x<<" "<<a[i+1].y<<endl;
		lasi=i+1;
	}
}

inline void coladd(int y)
{
	if(a[lasi+1].y!=y) return ;
	lasi++;
	for(int i=lasi;i<=m;i++)
	{
		if(a[i+1].y!=y) return ;
		addedge(a[i].bh,a[i+1].bh,(a[i+1].x-a[i].x)*2);
		addedge(a[i+1].bh,a[i].bh,(a[i+1].x-a[i].x)*2);
		//cout<<a[i].bh<<" "<<a[i+1].bh<<endl;
		//cout<<a[i].x<<" "<<a[i].y<<" "<<a[i+1].x<<" "<<a[i+1].y<<endl;
		lasi=i+1;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	register int i,j;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y;
		a[i].bh=i;
	}
	m++; cin>>a[m].x>>a[m].y; a[m].bh=m;
	m++; cin>>a[m].x>>a[m].y; a[m].bh=m;
	sort(a+1,a+m+1,colcmp);
	for(i=1;i<=n;i++) coladd(i);
	sort(a+1,a+m+1,rowcmp);
	lasi=0; for(i=1;i<=n;i++) rowadd(i);
	for(i=1;i<=m;i++) addedge(i,f(i),1),addedge(f(i),i,1);
	dij(m-1);
	int ans=min(dis[m],dis[f(m)]);
	if(ans==0x3f3f3f3f) cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}