HDU4587--TWO NODES(无向图割点,暴力出奇迹)这是我见过的时间最长的题。。。
TWO NODES
Time Limit: 24000/12000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2072 Accepted Submission(s): 683
Problem Description
Suppose that G is an undirected graph, and the value of stab is defined as follows:
Among the expression,G-i, -j is the remainder after removing node i, node j and all edges that are directly relevant to the previous two nodes. cntCompent is the number of connected components of X independently.
Thus, given a certain undirected graph G, you are supposed to calculating the value of stab.
Input
The input will contain the description of several graphs. For each graph, the description consist of an integer N for the number of nodes, an integer M for the number of edges, and M pairs of integers for edges (3<=N,M<=5000).
Please note that the endpoints of edge is marked in the range of [0,N-1], and input cases ends with EOF.
Output
For each graph in the input, you should output the value of stab.
Sample Input
4 5
0 1
1 2
2 3
3 0
0 2
Sample Output
2
Source
Recommend
zhuyuanchen520
/**********************我是分割线**************************/
12000秒,见过的时间最长的题目,发篇博客纪念一下
/**********************我是分割线**************************/
题意:
给你一个无向图,问你从这个无向图中删除任意两个点之后所能获得的独立连通分量个数的最大值.
分析:
12000秒,500个点,不暴一下真的对不起出题人。。。。
枚举要删的第一个点,然后Tarjan,Tarjan完事之后在找到删掉之后增加最多联通分量的点
代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int MAXN = 10010;
4 const int MAXM = 100010;
5 struct Edge
6 {
7 int to, next;
8 bool cut;//是否为桥的标记
9 } edge[MAXM];
10 int head[MAXN], tot;
11 int Low[MAXN]; //low记录了某个点能到达的最晚标号
12 int DFN[MAXN]; //某个点遍历到的标号
13 int Index, top; //DFS的时钟
14 bool cut[MAXN]; //记录某个点是否是割顶
15 int add_block[MAXN]; //删除一个点后增加的连通块
16 int bridge;
17 void addedge(int u, int v)
18 {
19 edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut = false;
20 head[u] = tot++;
21 }
22 void Tarjan(int u, int pre,int f)
23 {
24 //cout<<333333<<endl;
25 int v;
26
27 Low[u] = DFN[u] = ++Index;
28
29 int son = 0;
30 for (int i = head[u]; i != -1; i = edge[i].next)
31 {
32 v = edge[i].to;
33 if (v == pre)continue;
34 if (v == f) continue;
35 if ( !DFN[v] )
36 {
37 son++;
38 Tarjan(v, u,f);
39 if (Low[u] > Low[v]) Low[u] = Low[v];
40 //割点
41 //一个顶点u是割点,当且仅当满足(1)或(2) (1) u为树根,且u有多于一个子树。
42 //(2) u不为树根,且满足存在(u,v)为树枝边(或称父子边,
43 //即u为v在搜索树中的父亲),使得DFS(u)<=Low(v)
44 if (u != pre && Low[v] >= DFN[u]) //不是树根
45 {
46 cut[u] = true;
47 add_block[u]++;
48 }
49 }
50 else if ( Low[u] > DFN[v]) //!!!
51 Low[u] = DFN[v];
52 }
53 //树根,分支数大于1
54 if (u == pre && son > 1)cut[u] = true;
55 if (u == pre)add_block[u] = son - 1;
56
57 }
58 int solve(int N)
59 {
60 int ori=0;
61 int ans = -1;
62 for(int j=0;j<N;j++){
63 ori=0;
64 memset(DFN,0,sizeof(DFN));
65 memset(add_block,0,sizeof(add_block));
66 memset(cut,false,sizeof(cut));
67 Index = top = 0;
68 bridge = 0;
69 for(int i = 0;i< N;i++)
70 if(i!=j&&!DFN[i]){
71 ori++;
72 Tarjan(i,i,j);
73 }
74 for(int i = 0;i <N;i++){
75 if(i!=j)
76 ans=max(ans,add_block[i]+ori);
77 }
78 }
79 return ans;
80 }
81
82 int main()
83 {
84 int n,m;
85 int u,v;
86 while(~scanf("%d%d",&n,&m)){
87 memset(head,-1,sizeof(head));
88 tot=0;
89 for(int i=0;i<m;i++){
90 scanf("%d%d",&u,&v);
91 addedge(u,v);
92 addedge(v,u);
93 }
94 printf("%d\n",solve(n));
95 }
96 }
97
最新文章
- Java 批量插入数据(Oracle)
- 自己写的基于bootstrap风格的弹框插件
- Linuxmint&;win7
- 使用powerdesigner创建数据库表
- ProcessOn:功能强大的在线作图工具(HTML5)
- 桶排序-Swift
- android系统中使用TelephonyManager类来获取imei号和其他手机信息
- bash 统计文件行数
- 普通Windows控制台窗口运行nmake编译VC
- c语言学习之基础知识点介绍(十):内存空间模型、地址解释及指针变量
- UITableView出现卡顿如何处理
- ZYB&#39;s Game(博弈)
- js中关于string的一些常用的方法
- ListView 无 DataSource 依然用 DataPager 翻页
- [洛谷]P3729 曼哈顿计划EX(最小割树/等价流树)
- 1.JAVA-Hello World
- 翻译:CONCURRENT INSERTS(已提交到MariaDB官方手册)
- mysql命令大全用户管理相关命令
- Installation of Scylla on CentOS 7
- zabbix3.2的server和zabbix-agent2.2怎么监控MySQL的办法