题目:题目链接
这道题目的意思就是说给你一幅图,然后你可以往这个图里面添加边。要求就是你插入边之后不能产生重复边和环,并且不能形成强联通图。问你最多可以添加多少条边?
分析:我们可以这样判断,就是说我们添加完所有能加入的边之后,我们可以把这时候形成的图分成两部分,比如
x,y;这是一定可以有只有从x到y的边,木有Y到x的。同时x,y均为完全图。假设两者中各有点数a,b.则有a+b==n;按照
联通图的定义,我们可以得到总的边数为sum = x*(x+1) + y(y-1)+x*y;就是x内部的边加上y内部的边在加上x,y之间
的边。合并之后有sum = n*n-n-a*b;要使sum尽量大,则a,b需要差距尽量大.我们把原先的图缩点(刚刚学习的,囧
(/ □ \)),得到若干个联通分量。如果某个出度/入度为0,那么就可以作为一部分。当然,要是这个部分的点数越
小越好。然后从这个部分填边这时候能拥有的边数是最多的。
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> using namespace std; #define N 100010 int n,m; int sumliantong; int DFS[N]; int input[N]; int output[N]; int low[N]; int cnt[N]; int index; bool vis[N]; int num[N]; vector<int>L[N]; stack<int>S; struct node { int l,r; } link[N]; void tarjan(int x) { DFS[x] = low[x] = index++; vis[x] = true; S.push(x);//x入栈,沿着x找链接点 for(int i = 0; i <(int)L[x].size(); ++i) { int tp = L[x][i]; if(!DFS[tp])//如果没有计算联通 { tarjan(tp);//找这个点的联通 low[x] = min(low[x], low[tp]);//找链接的节点数小的 } else if(vis[tp] && low[x] > DFS[tp]) low[x] = DFS[tp]; } if(DFS[x] == low[x]) { sumliantong++;//计算强联通量个数 int i; for(i = S.top(), S.pop(); i != x; i = S.top(),S.pop()) { cnt[i] = sumliantong;//这些都属于sumliantong vis[i] = false; } cnt[i] = sumliantong; vis[i] = false; } } __int64 work() { for(int i = 1; i <= n; ++i)//找强联通分量 { if(!DFS[i])//是否已经属于某一个联通分量 tarjan(i); } if(sumliantong == 1) return -1; memset(input, 0, sizeof(input));//入度 memset(output, 0, sizeof(output));//出度 for(int i = 0; i < m; ++i) { if(cnt[link[i].l] == cnt[link[i].r])//属于同一联通图 continue; output[cnt[link[i].l]] ++;//计算此联通量的出度 input[cnt[link[i].r]] ++;//同理入度 } memset(num, 0, sizeof(num)); for(int i = 1; i <=n; ++i)//属于每个强联通的数量 num[cnt[i]] ++; __int64 ans = -1; for(int i = 1; i <= sumliantong; ++i) { if(input[i] == 0 || output[i] == 0) { int a = num[i]; int b = n - num[i]; if(a == 1 || b == 1) return 1ll * (n-1) * (n-1) - m; else ans = max(1ll * a * (a-1) + 1ll * b * (b-1) + 1ll * a * b - m, ans);//取最大 } } return ans; } int main() { int t; scanf("%d", &t); int cpp = 1; //case标记 int a, b; while(t--) { index = 1; sumliantong = 0; scanf("%d%d", &n, &m); memset(DFS, 0, sizeof(DFS)); for(int i = 0; i <= n; ++i)//清空 L[i].clear(); for(int i = 0; i < m; ++i) { scanf("%d%d", &a, &b); link[i].l = a; link[i].r = b; L[a].push_back(b);//链接 } __int64 ans = work(); printf("Case %d: %I64d\n", cpp++, ans); } return 0; }