P1330-封锁阳光大学

傷城~ 2023-06-01 08:54 14阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define pb push_back
     6 typedef long long ll;
     7 using namespace std;
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 
    24 #define pb push_back
    25 const int maxn = 100003; 
    26 vector<int> G[maxn];
    27 int ans = 0;
    28 int V;
    29 int color[maxn];
    30 int a,b;
    31 bool dfs(int v,int c)
    32 {
    33     color[v] = c;
    34     if(c==1)
    35         a ++;
    36     else
    37         b ++;
    38     for(int i = 0;i < G[v].size();i ++)
    39     {
    40         if(color[G[v][i]] == c) return false;
    41         if(color[G[v][i]] == 0 && !dfs(G[v][i],-c)) return false;
    42     }
    43     return true;
    44 }
    45 int biGraph()
    46 {
    47     memset(color,0,sizeof(color));
    48     for(int i = 1;i < V+1;i ++)
    49     {
    50         a = 0,b = 0;
    51         if(color[i]==0)
    52             if(!dfs(i,1))
    53                 return 0;
    54         ans += min(a,b);
    55     }
    56     return 1;
    57 }
    58 int M;
    59 
    60 int main()
    61 {
    62     V = read();
    63     M = read();
    64     
    65      _for(i,0,M)
    66     {
    67         int a = read(),b = read();
    68         G[a].pb(b);
    69         G[b].pb(a);
    70     }
    71     
    72     int rnt = biGraph();
    73     int rnt1 = 0,rnt2 = 0;
    74     if(!rnt)
    75     {
    76         printf("Impossible\n");
    77         return 0;
    78     }
    79     else
    80         printf("%d\n",ans);
    81     
    82     return 0;
    83 }

转载于:https://www.cnblogs.com/Asurudo/p/11504374.html