#C241122B. 三角图

标签（Label）

• 欧拉回路

网址（Website）

题目详情 - 三角图 - Super

题解 - 三角图 - Super

题目（Problem）

输入数据 1

4
4
4 2
1 2 3
4
1 2
1 3 3
2
4 3
1 4 3

输出数据 1

38

输入数据 2

5
9
3 9
4 8 7
6 6 7 5
3
9 3
7 7 5
8 4 6 8
9
7 5
9 8 3
8 7 6 4

输出数据 2

171

【样例3】

见选手目录下的 $triangle/triangle3.in$ 与 $triangle/triangle3.ans$。

【样例4】

见选手目录下的 $triangle/triangle4.in$ 与 $triangle/triangle4.ans$。

【样例5】

见选手目录下的 $triangle/triangle5.in$ 与 $triangle/triangle5.ans$。

题解（Solution）

这个东西肯定满足欧拉回路，欧拉回路的性质是每个点的度都是偶数，因此我们完全可以直接一笔画走完整张图并且走回 $(1,1)$ ，这个时候我们需要从 $(1,1)$ 走到 $(n,n)$ ，说白了就是加上从 $(1,1)$ 到 $(n,n)$ 的路径，我们就能走出一条完整的欧拉回路，最后的答案肯定就是边权和减去 $(1,1)\to(n,n)$ 的路径，那我们肯定要让这条路径最短，直接求最短路即可。

还有一个点我在考试的时候忽略了，就是会不会求出的路径使得剩下的路径无法连通，实际上因为由于数据范围中三角形的限制，所以对于一个三角形最短路最多经过一条边，一定会存在剩下两条边组成剩余路径，证毕。

出题者题解

代码（Code）

100分

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ROf(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n';
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 2005;
bool ST;double Tim;

/*
对于一个正方形（斜着的） 
可以从 (i,j) 走完整个正方形走到 (i+k,j+k)  ?
这就是欧拉回路的拓展
想到了入度和出度
因为这张图一定构成一张欧拉回路，所以从(1,1)走出一定可以回来
所以如果要到(n,n)就必须钦定一条从(n,n)回来的路，减去这条路的贡献
就变成了求最短路 
*/

int cha[N][N],cnt;//转成一维的点 
vector<P> ft[N*N];
int n,all;

priority_queue<P> q;
int dis[N*N];
void dijkstra(int st){
	memset(dis,0x3f,sizeof dis);
	dis[st] = 0, q.emplace(0,st);
	while(q.size()){
		int x=q.top().y;q.pop();
		for(auto p:ft[x]){
			int y,v;tie(y,v)=p;
			if(dis[x]+v < dis[y]){
				dis[y] = dis[x]+v;
				q.emplace(-dis[y],y);
			}
		}
	}
}

void Solve(){
	n=rd();For(i,1,n) For(j,1,i) cha[i][j]=++cnt;
	For(i,1,n-1) For(j,1,i){
		int x=cha[i][j], y=cha[i+1][j], v=rd();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
		all+=v;
	}
	For(i,1,n-1) For(j,1,i){
		int x=cha[i][j], y=cha[i+1][j+1], v=rd();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
		all+=v;
	}
	For(i,1,n-1) For(j,1,i){
		int x=cha[i+1][j], y=cha[i+1][j+1], v=rd();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
		all+=v;
	}
	dijkstra(1);
	write(all-dis[cnt]), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("triangle.in","r",stdin);
	freopen("triangle.out","w",stdout);
	int Tt=1;Tim = clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}