[HAOI2017]新型城市化

题目描述

Anihc国有n座城市.城市之间存在若一些贸易合作关系.如果城市x与城市y之间存在贸易协定.那么城市文和城市y则是一对贸易伙伴(注意:(x,y)和(y,x))是同一对城市)。

为了实现新型城市化.实现统筹城乡一体化以及发挥城市群辐射与带动作用.国 决定规划新型城市关系。一些城市能够被称为城市群的条件是:这些城市两两都是贸易伙伴。 由于Anihc国之前也一直很重视城市关系建设.所以可以保证在目前已存在的贸易合作关系的情况下Anihc的n座城市可以恰好被划分为不超过两个城市群。

为了建设新型城市关系Anihc国想要选出两个之前并不是贸易伙伴的城市.使这两个城市成为贸易伙伴.并且要求在这两个城市成为贸易伙伴之后.最大城市群的大小至少比他们成为贸易伙伴之前的最大城市群的大小增加1。

Anihc国需要在下一次会议上讨论扩大建设新型城市关系的问题.所以要请你求出在哪些城市之间建立贸易伙伴关系可以使得这个条件成立.即建立此关系前后的最大城市群的 大小至少相差1。

输入输出格式

输入格式：

第一行2个整数n,m.表示城市的个数,目前还没有建立贸易伙伴关系的城市的对数。

接下来m行,每行2个整数x,y表示城市x,y之间目前还没有建立贸易伙伴关系。

输出格式：

第一行yi个整数ans，表示符合条件的城市的对数.注意(x,y)与(y,x)算同一对城市。

接下来Ans行,每行两个整数,表示一对可以选择来建立贸易伙伴关系的城市。对于 一对城市x,y请先输出编号更小的那一个。最后城市对与城市对之间顺序请按照字典序从小到大输出。

输入输出样例

输入样例#1：

5 3
1 5
2 4
2 5

输出样例#1：

2
1 5
2 4

说明

数据规模与约定

数据点1： n≤16

数据点2： n≤16

数据点3~5： n≤100

数据点6： n≤500

数据点7~10： n≤10000

对于所有的数据保证：n <= 10000,0 <= m <= min (150000,n(n-1)/2).保证输入的城市关系中不会出现(x,x)这样的关系.同一对城市也不会出现两次(无重边.无自环)。

题解

为啥这种题我也想不出来==
最近感觉水平越来越低了
首先看题目要求:\(n\)个点可以被恰好分为两个团
那么这就意味着这玩意儿的反图一定是一个二分图
那么这就是一个二分图的匹配问题了
先二分图染色确定每个点是与\(S\)还是与\(T\)连
然后跑\(dinic\)
再看题目的要求,连上这条边以后最大团大小至少+1
那么问题也就转化成了每条边是否是最大匹配的必须边
那么判断方式就是在残留网络上跑\(tarjan\)
如果一条边的两个端点不在同一个强联通分量中并且这条边满流,那么这条边就是必须边了

代码

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define MP(x , y) make_pair(x , y)
const int M = 10050 ;
const int INF = 1e9 ;
using namespace std ;

inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
    return x*w ;
}

bool exist[M] , Est[M] ;
int n , m , num = 1 , S , T , idt ;
int idx[M] , hea[M] , d[M] , efr[M * 30] , eto[M * 30] ;
int cnt , top , bnum , dfn[M] , low[M] , st[M] , bel[M] , eid[M * 30] ;
pair < int , int > ans[M * 30] ;
vector < int > vec[M] ;
struct E { int nxt , to , dis ; } edge[M * 50] ;
inline bool cmp(pair< int , int > a , pair< int , int > b) {
    if(a.first == b.first)
        return a.second < b.second ;
    else return a.first < b.first ;
}
inline void Insert_edge(int from , int to , int dis) {
    edge[++num].nxt = hea[from] ; edge[num].to = to ;
    edge[num].dis = dis ; hea[from] = num ;
}
inline void add_edge(int u , int v , int w) {
    Insert_edge(u , v , w) ;
    Insert_edge(v , u , 0) ;
}

inline bool bfs() {
    queue < int > q ; q.push(S) ; memset(d , 0 , sizeof(d)) ; d[S] = 1 ;
    while(!q.empty()) {
        int u = q.front() ; q.pop() ;
        for(int i = hea[u] ; i ; i = edge[i].nxt) {
            int v = edge[i].to ; 
            if(!d[v] && edge[i].dis > 0) {
                d[v] = d[u] + 1 ; q.push(v) ;
                if(v == T) return true ;
            }
        }
    }
    return d[T] ;
}
int Dfs(int u , int dis) {
    if(u == T || !dis) return dis ; int sum = 0 ;
    for(int i = hea[u] ; i ; i = edge[i].nxt) {
        int v = edge[i].to ; if(d[v] == d[u] + 1 && edge[i].dis > 0) {
            int diss = Dfs(v , min(dis , edge[i].dis)) ;
            if(diss > 0) {
                edge[i].dis -= diss ; edge[i ^ 1].dis += diss ;
                sum += diss ; dis -= diss ; if(!dis) break ;
            }
        }
    }
    if(!sum) d[u] = -1 ; return sum ;
}
inline void dinic() {
    while(bfs())
        Dfs(S , INF) ;
}

void dfs(int u , int col) {
    idx[u] = col ;
    for(int i = 0 , v ; i < vec[u].size() ; i ++) {
        v = vec[u][i] ; if(idx[v]) continue ;
        dfs(v , (col ^ 1)) ;
    }
}
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt ; st[++top] = u ; exist[u] = true ;
    for(int i = hea[u] ; i ; i = edge[i].nxt) {
        int v = edge[i].to ; 
        if(!edge[i].dis) continue ;
        if(!dfn[v]) {
            tarjan(v) ;
            low[u] = min(low[u] , low[v]) ;
        }
        if(exist[v]) low[u] = min(low[u] , dfn[v]) ;
    }
    if(dfn[u] == low[u]) {
        ++ bnum ;
        while(st[top + 1] != u) {
            bel[st[top]] = bnum ;
            exist[st[top --]] = false ;
        }
    }
}

int main() {
    n = read() ; m = read() ; 
    S = 10002 ; T = 10003 ;
    for(int i = 1 ; i <= m ; i ++)  {
        efr[i] = read() ; eto[i] = read() ;
        if(efr[i] > eto[i]) swap(efr[i] , eto[i]) ;
        vec[efr[i]].push_back(eto[i]) ;
        vec[eto[i]].push_back(efr[i]) ;
    }
    for(int i = 1 ; i <= n ; i ++)
        if(!idx[i])
            dfs(i , S) ;
    for(int i = 1 ; i <= n ; i ++) 
        if(idx[i] == S) add_edge(S , i , 1) ;
        else add_edge(i , T , 1) ;
    for(int i = 1 , u , v ; i <= m ; i ++) {
        u = efr[i] , v = eto[i] ;
        if(idx[u] == S) add_edge(u , v , 1) ;
        else add_edge(v , u , 1) ;
        eid[i] = num ; 
    }
    dinic() ;
    for(int i = 1 ; i <= n ; i ++)
        if(!dfn[i])
            tarjan(i) ;
    for(int i = 1 ; i <= m ; i ++)
        if(bel[efr[i]] != bel[eto[i]] && edge[eid[i]].dis > 0)
            ans[++idt] = MP(efr[i] , eto[i]) ;
    printf("%d\n",idt) ;
    sort(ans + 1 , ans + idt + 1 , cmp) ;
    for(int i = 1 ; i <= idt ; i ++)
        printf("%d %d\n",ans[i].first , ans[i].second) ;
    return 0 ;
}

[HAOI2017]新型城市化

原文：https://www.cnblogs.com/beretty/p/10725927.html