10801: 帝国交通
题目描述
围绕新校的操场建有 m(1 到 1000) 个蚂蚁王国, 根据相邻关系依次编号为 1..m. 其中有 n(1 到 10000) 对王国的国王之间有亲戚关系, 有亲戚关系的王国需要有道路相通 (可以以其它王国作为中转), 任何一条道路只能建在相邻的两个王国之间, 求出至少需要建多少条道路才能满足这 n 对王国的需求.
输入说明: 第 1 行 m n ; 第 2 行到第 n+1 行, 每行两个数字, 描述有亲戚关系的两个王国编号.
输入
第 1 行 m n ; 第 2 行到第 n+1 行, 每行两个数字, 描述有亲戚关系的两个王国编号.
输出
1 个数字, 最少需要修建的道路数.
样例输入
复制样例数据
5 2 1 3 4 5
样例输出
3
思路: 将环转化成链
枚举每一个点为断点 将一个环切成一条链 断点为初始点 前一个点为终点
断点意味着连边的时候不能跨过这个断点 只能向 "后" 连
然后暴力连好边之后每次计数连接边数 取最小
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 10005;
- const int maxm = 1005;
- struct node{
- int u,v; //u>v
- }edge[maxn];
- int point[maxm];
- int main()
- {
- int n,m;
- scanf("%d%d",&m,&n);
- for(int i=1;i<=n;i++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- int a = max(x,y),b= min(x,y);
- edge[i] = (node){a,b};
- }
- int ans = m;
- for(int i=1;i<=m;i++)
- {
- memset(point,0,sizeof(point));
- int now = 0;
- int posv,posu;
- for(int j=1;j<=n;j++)
- {
- if(edge[j].v>=i)
- {
- posu = edge[j].u-i+1;
- posv = edge[j].v-i+1;
- point[posv]++;
- point[posu]--;
- }
- else if(edge[j].v<=i-1&&edge[j].u>=i)
- {
- posu = edge[j].u-i+1;
- posv = m-i+1+edge[j].v;
- point[posu]++;
- point[posv]--;
- }
- else
- {
- posv = m-i+1+edge[j].v;
- posu = m-i+1+edge[j].u;
- point[posv]++;
- point[posu]--;
- }
- }
- for(int j=1;j<m;j++)
- {
- point[j]+=point[j-1];
- if(point[j]>0)
- now++;
- }
- ans = min(ans,now);
- }
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2931597.html