Description
Input
Output
Sample Input
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
0 15 9 20 25 8 10 13 17 8 8 7
15 0 12 12 10 10 8 15 15 8 8 9
9 12 0 25 20 18 16 14 13 7 12 12
20 12 25 0 8 13 14 15 15 10 10 10
25 10 20 8 0 16 20 18 17 18 9 11
8 10 18 13 16 0 10 9 11 10 8 12
10 8 16 14 20 10 0 18 20 6 16 15
13 15 14 15 18 9 18 0 5 12 12 13
17 15 13 15 17 11 20 5 0 22 8 10
8 8 7 10 18 10 6 12 22 0 11 12
8 8 12 10 9 8 16 12 8 11 0 9
7 9 12 10 11 12 15 13 10 12 9 0
Sample Output
HINT
题意难理解大概是这题目通过人数少的根本原因吧……
并查集直接求出多边形数,然后直接跑出路径就好了吧
写完代码改完编译错误立刻过样例了……233……然后立刻就交了
只有20人A的题目居然1A了……
#include<cstdio>
#include<algorithm>
using namespace std; int n,m,f[][],fa[],i,j,a,x,y,g[],num=,ans=1e8,an;
char c;
int read(){
a=;
c=getchar();
while(c<''||c>'') c=getchar();
while(c>=''&&c<='') a=a*+c-,c=getchar();
return a;
}
int gf(int x){
if (x==fa[x]) return x;else{
fa[x]=gf(fa[x]);
return fa[x];
}
}
int main(){
scanf("%d",&n);
for (i=;i<=n;i++) fa[i]=i;
for (i=;i<=n;i++){
x=gf(read());y=gf(read());
if (x!=y) fa[x]=y;
}
for(i=;i<=n;i++) if (i==gf(i)) g[i]=++num;
for(i=;i<=n;i++) g[i]=g[gf(i)];
for (i=;i<=n;i++)
for (j=;j<=n;j++) f[i][j]=;
for (i=;i<=n;i++)
for (j=;j<=n;j++)
f[g[i]][g[j]]=min(f[g[i]][g[j]],read());
for (i=;i<=num;i++){
an=;
for (j=;j<=num;j++) an+=f[i][j];
if (an<ans) ans=an;
}
printf("%d\n",ans<<);
}
bzoj:3397 [Usaco2009 Feb]Surround the Islands 环岛篱笆的更多相关文章
-
【BZOJ】3397: [Usaco2009 Feb]Surround the Islands 环岛篱笆(tarjan)
http://www.lydsy.com/JudgeOnline/problem.php?id=3397 显然先tarjan缩点,然后从枚举每一个scc,然后向其它岛屿连费用最小的边,然后算最小的即可 ...
-
BZOJ3397: [Usaco2009 Feb]Surround the Islands 环岛篱笆
3397: [Usaco2009 Feb]Surround the Islands 环岛篱笆 Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 11 So ...
-
Bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级 dijkstra,堆,分层图
1579: [Usaco2009 Feb]Revamping Trails 道路升级 Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1573 Solv ...
-
BZOJ 1579: [Usaco2009 Feb]Revamping Trails 道路升级( 最短路 )
最短路...多加一维表示更新了多少条路 -------------------------------------------------------------------------------- ...
-
BZOJ 1578: [Usaco2009 Feb]Stock Market 股票市场( 背包dp )
我们假设每天买完第二天就卖掉( 不卖出也可以看作是卖出后再买入 ), 这样就是变成了一个完全背包问题了, 股票价格为体积, 第二天的股票价格 - 今天股票价格为价值.... 然后就一天一天dp... ...
-
BZOJ 3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛( dp )
水题...忘了取模就没1A了.... --------------------------------------------------------------------------- #incl ...
-
bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级 -- 分层图最短路
1579: [Usaco2009 Feb]Revamping Trails 道路升级 Time Limit: 10 Sec Memory Limit: 64 MB Description 每天,农夫 ...
-
bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级 优先队列+dij
1579: [Usaco2009 Feb]Revamping Trails 道路升级 Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1768 Solv ...
-
bzoj:1723: [Usaco2009 Feb]The Leprechaun 寻宝
Description 你难以想象贝茜看到一只妖精在牧场出现时是多么的惊讶.她不是傻瓜,立即猛扑过去,用她那灵活的牛蹄抓住了那只妖精. “你可以许一个愿望,傻大个儿!”妖精说. “财富 ...
随机推荐
-
rsync传输性能测试总结 转
测试环境 1.1服务器硬件信息 1.2 服务器软件信息 1.3 Rsync所能够支持的功能 (1)支持断点续传 (2)支持使用ssh传输加密 (3)支持128位MD4校验(3.0以后版本使用MD5加密 ...
-
fhq_treap 总结
今天跟着zcg大神学了一发fhq_treap 发现在维护区间问题上fhq_treap不仅思维量小,而且代码量更小 是Splay的不错的替代品,不过至今还是有一些问题不能很好的解决 譬如查询某个数在序列 ...
-
angularjs填写表单
https://scotch.io/tutorials/handling-checkboxes-and-radio-buttons-in-angular-forms <!DOCTYPE html ...
-
Flink Program Guide (8) -- Working with State :Fault Tolerance(DataStream API编程指导 -- For Java)
Working with State 本文翻译自Streaming Guide/ Fault Tolerance / Working with State ---------------------- ...
-
jQuery.fn.extend与jQuery.extend 的区别
1 jquery.extend 是jquery 静态的方法 实例 jQuery.extend({ liu: function(){ alert('liu'); } }) ...
-
Java报错信息 java.lang.SecurityException: Prohibited package name: java.xxx
package java.yun.System; public class SystemOut { public static void main(String[] args) { System.ou ...
-
冰水挑战 HDU - 6495
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6495 题解:DP!!! dp[i][j] 表示前i个挑战,接受了j个剩余的最大体力,最后输出体力大于0 ...
-
比较json和fastjson的put()
首先,分别运行下面两段json和fastjson的代码: import org.json.JSONException; import org.json.JSONObject; public class ...
-
web开发路径问题解决
使用监听器解决路径问题 监听器:
-
Kotlin——中级篇(五):枚举类(Enum)、接口类(Interface)详解
在上一章节中,详细的类(class)做了一个实例讲解,提到了类(class)的实例化.构造函数.声明.实现方式.和Java中类的区别等.但是对于Kotlin中的类的使用还远远不止那些.并且在上文中提到 ...