闭会算法好题之2020ICPC澳门站签到A题
题意想起来这是昆明站前一天和队友模的，好像当时看了大概有小一个小时，就是想不到，突然想到的瞬间和队友一说，我们就一拍脑门同时说我是s~b！
那到底是啥思路让我和我的队友直呼我是s ~b？
首先理一理这题的大概思路，题意是说要你用一个1-n的全排列然后填满一个n*n的正方形矩阵，然后自己确定一个起点，然后上下左右走，全部走完整条路，然后输出一条路径，路径的要求是你从权值较小的点转移到权值较大的点的次数要求要比从权值大的到小的次数要少，可以理解为上坡要比下坡少。
这里就需要思考了，如何才能把整条路径走完了，是不是从最大的点开始走就最优的呢？
其实如果你想到了先找把路径走完的方案，再去考虑限制条件，可能能少很多弯路，那保证能一定走完，直接的想法肯定是从开头或者结尾一直走就行了，当然不要选择从中间开始像蛇形填数的那种恶心自己的走法！
那么路径确定好了，如何保证上坡比下坡少呢？
仔细的想一想，既然起点可以自己定，那你定在(1,1)开头，然后以S型走法把整个迷宫走完，可以得到一个路径，和一个上坡次数和下坡次数，如果符合条件直接输出即可，这里不符合条件的话，你把开头和结尾调换一下，从尾走到头，是不是也把上下坡同时调换了，那么你就一定可以得到一个上坡次数小于等于下坡次数的路径啦~（这里还推荐一下澳门站的k题并查集+dfs搜路径的好题，因为记录点的问题，这场就做出一题了悲）
贴份代码：
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m;
#define MAX 100009
vector<vector<pair<int,int> > >v(MAX);
vector<int>ans;
int d[MAX];
bool vis[MAX];
int dsu(int num)
{
if(num==d[num])
return num;
return d[num]=dsu(d[num]);
}
int connect(int a,int b)
{
int ma=dsu(a);
int mb=dsu(b);
if(ma==mb)
return -1;
else
{
d[ma]=mb;
return 0;
}
}
int dfs(int node,int st,int ed)
{
int i,j,flag=0,num;
for(i=0;i<v[node].size();i++)
{
int nx=v[node][i].first;
if(nx==ed)
{
ans.push_back(v[node][i].second);
return nx;
}
if(vis[nx]==0)
{
vis[nx]=1;
num= dfs(nx,st,ed);
if(num!=-1)
{
ans.push_back(v[node][i].second);
if(node!=st)
return node;
else
return -1;
}
vis[nx]=0;
}
}
return -1;
}
int main()
{
int i,j,t;
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n>>m;
ans.clear();
for(i=1;i<=n;i++)
{
d[i]=i;
v[i].clear();
vis[i]=0;
}
int ok=1;
for(i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
if(ok)
{
int res=connect(a,b);
if(res==-1)
{
dfs(a,a,b);
if(ans.size()!=0)
ans.push_back(i+1);
ok=0;
}
v[a].push_back(make_pair(b,i+1));
v[b].push_back(make_pair(a,i+1));
}
}
if(ans.size()!=0)
{
sort(ans.begin(),ans.end());
cout<<ans[0];
for(i=1;i<ans.size();i++)
cout<<" "<<ans[i];
cout<<endl;
}
else
cout<<-1<<endl;
}
return 0;
}
/*
1
6 8
1 2
1 2
1 2
2 3
5 6
3 4
2 5
5 4
*/ 
查看17道真题和解析
