2022牛客五一集训派对day1（E、H）

E-Touring cities

链接：https://ac.nowcoder.com/acm/contest/33549/E
来源：牛客网
题目：
Niuniu wants to tour the cities in Moe country. Moe country has a total of nm cities. The positions of the cities form a grid with n rows and m columns. We represent the city in row x and column y as (x,y). (1 ≤ x ≤ n,1 ≤ y ≤ m) There are bidirectional railways between adjacent cities. (x1,y1) and (x2,y2) are called adjacent if and only if |x1-x2|+|y1-y2|=1. There are also K bidirectional air lines between K pairs of cities. It takes Niuniu exactly one day to travel by a single line of railway or airplane. Niuniu starts and ends his tour in (1,1). What is the minimal time Niuniu has to travel between cities so that he can visit every city at least once?
Note that the air line may start and end in the same city.
题意：
给一个nm的矩形，相邻的方格之间连边，在给k组x1,y1,x2,y2（x1,y1）和（x2,y2）连边，从（1,1）走到（1,1），需要经过所有的方格每次移动一个方格需要1天时间，输出走完这些的最小的天数。
思路：
通过画图自己手动模拟可以发现当n和m不同时为奇数的时候输出nm就是答案，当n和m都为奇数的时候，发现可以构造出nm+1的答案，我们把整张图从（1,1）开始黑白染色当两个黑色块之间有一条边的情况是这个图还是可以构成哈密顿回路既答案可以为n*m，所以我们只需要判断是否有两个黑块存在边就行。
以下为ac代码：

#include
typedef long long ll;
typedef unsigned long long ull;
#define int ll
#define pii pair<int,int>
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-8;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int LINF=0x3f3f3f3f3f3f3f3f;
const int MAXN=2e5+10;
void solve()
{int n,m,k;cin>>n>>m>>k;if((n&1)&&(m&1)){int ans=n*m+1;int flag=0;for(int i=1;i<=k;++i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！