bzoj:3397 [Usaco2009 Feb]Surround the Islands 环岛篱笆

时间:2021-09-02 08:18:17

Description

    约翰在加勒比海买下地产,准备在这里的若干个岛屿上养奶牛.所以,他要给所有岛屿围上篱笆.每个岛屿都是多边形.他沿着岛屿的一条边界朝一个方向走,有时候坐船到另一个岛去.他可以从任意一个多边形顶点开始修篱笆的工作;在任意一个到达的顶点,他可以坐船去另一个岛屿的某个顶点,但修完那个岛的篱笆,他必须马上原路返回这个出发的岛屿顶点.任意两个顶点间都有肮线,每条航线都需要一定的费用.请帮约翰计算最少的费用,让他修完所有篱笆.

Input

    第1行输入N(3≤N≤500),表示所有岛屿多边形的个数.
    接下来N行每行输入两个整数V1和V2(1≤V1≤N;1≤V2≤N),表示一条构成岛屿的线段的两个端点.接下来输入N行N列的矩阵,表示两个顶点间航行所需费用.

Output

 
    一个整数,最少费用.

Sample Input

12
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

30

HINT

bzoj:3397 [Usaco2009 Feb]Surround the Islands 环岛篱笆

bzoj:3397 [Usaco2009 Feb]Surround the Islands 环岛篱笆

题意难理解大概是这题目通过人数少的根本原因吧……

并查集直接求出多边形数,然后直接跑出路径就好了吧

写完代码改完编译错误立刻过样例了……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 环岛篱笆的更多相关文章

  1. 【BZOJ】3397&colon; &lbrack;Usaco2009 Feb&rsqb;Surround the Islands 环岛篱笆(tarjan)

    http://www.lydsy.com/JudgeOnline/problem.php?id=3397 显然先tarjan缩点,然后从枚举每一个scc,然后向其它岛屿连费用最小的边,然后算最小的即可 ...

  2. BZOJ3397&colon; &lbrack;Usaco2009 Feb&rsqb;Surround the Islands 环岛篱笆

    3397: [Usaco2009 Feb]Surround the Islands 环岛篱笆 Time Limit: 3 Sec  Memory Limit: 128 MBSubmit: 11  So ...

  3. Bzoj 1579&colon; &lbrack;Usaco2009 Feb&rsqb;Revamping Trails 道路升级 dijkstra&comma;堆&comma;分层图

    1579: [Usaco2009 Feb]Revamping Trails 道路升级 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1573  Solv ...

  4. BZOJ 1579&colon; &lbrack;Usaco2009 Feb&rsqb;Revamping Trails 道路升级&lpar; 最短路 &rpar;

    最短路...多加一维表示更新了多少条路 -------------------------------------------------------------------------------- ...

  5. BZOJ 1578&colon; &lbrack;Usaco2009 Feb&rsqb;Stock Market 股票市场&lpar; 背包dp &rpar;

    我们假设每天买完第二天就卖掉( 不卖出也可以看作是卖出后再买入 ), 这样就是变成了一个完全背包问题了, 股票价格为体积, 第二天的股票价格 - 今天股票价格为价值.... 然后就一天一天dp... ...

  6. BZOJ 3398&colon; &lbrack;Usaco2009 Feb&rsqb;Bullcow 牡牛和牝牛&lpar; dp &rpar;

    水题...忘了取模就没1A了.... --------------------------------------------------------------------------- #incl ...

  7. bzoj 1579&colon; &lbrack;Usaco2009 Feb&rsqb;Revamping Trails 道路升级 -- 分层图最短路

    1579: [Usaco2009 Feb]Revamping Trails 道路升级 Time Limit: 10 Sec  Memory Limit: 64 MB Description 每天,农夫 ...

  8. bzoj 1579&colon; &lbrack;Usaco2009 Feb&rsqb;Revamping Trails 道路升级 优先队列&plus;dij

    1579: [Usaco2009 Feb]Revamping Trails 道路升级 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1768  Solv ...

  9. bzoj&colon;1723&colon; &lbrack;Usaco2009 Feb&rsqb;The Leprechaun 寻宝

    Description 你难以想象贝茜看到一只妖精在牧场出现时是多么的惊讶.她不是傻瓜,立即猛扑过去,用她那灵活的牛蹄抓住了那只妖精.     “你可以许一个愿望,傻大个儿!”妖精说.     “财富 ...

随机推荐

  1. rsync传输性能测试总结 转

    测试环境 1.1服务器硬件信息 1.2 服务器软件信息 1.3 Rsync所能够支持的功能 (1)支持断点续传 (2)支持使用ssh传输加密 (3)支持128位MD4校验(3.0以后版本使用MD5加密 ...

  2. fhq&lowbar;treap 总结

    今天跟着zcg大神学了一发fhq_treap 发现在维护区间问题上fhq_treap不仅思维量小,而且代码量更小 是Splay的不错的替代品,不过至今还是有一些问题不能很好的解决 譬如查询某个数在序列 ...

  3. angularjs填写表单

    https://scotch.io/tutorials/handling-checkboxes-and-radio-buttons-in-angular-forms <!DOCTYPE html ...

  4. Flink Program Guide (8) -- Working with State &colon;Fault Tolerance(DataStream API编程指导 -- For Java)

    Working with State 本文翻译自Streaming Guide/ Fault Tolerance / Working with State ---------------------- ...

  5. jQuery&period;fn&period;extend与jQuery&period;extend 的区别

    1 jquery.extend 是jquery 静态的方法 实例 jQuery.extend({     liu: function(){         alert('liu');     } }) ...

  6. Java报错信息 java&period;lang&period;SecurityException&colon; Prohibited package name&colon; java&period;xxx

    package java.yun.System; public class SystemOut { public static void main(String[] args) { System.ou ...

  7. 冰水挑战 HDU - 6495

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6495 题解:DP!!! dp[i][j] 表示前i个挑战,接受了j个剩余的最大体力,最后输出体力大于0 ...

  8. 比较json和fastjson的put&lpar;&rpar;

    首先,分别运行下面两段json和fastjson的代码: import org.json.JSONException; import org.json.JSONObject; public class ...

  9. web开发路径问题解决

     使用监听器解决路径问题 监听器:

  10. Kotlin——中级篇(五):枚举类(Enum)、接口类(Interface)详解

    在上一章节中,详细的类(class)做了一个实例讲解,提到了类(class)的实例化.构造函数.声明.实现方式.和Java中类的区别等.但是对于Kotlin中的类的使用还远远不止那些.并且在上文中提到 ...