P1330 封锁阳光大学

题目描述

曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

输入输出格式

输入格式：

 

第一行：两个整数N，M

接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。

 

输出格式：

 

仅一行：如果河蟹无法封锁所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。

 

输入输出样例

输入样例#1：

3 31 21 32 3

输出样例#1：

Impossible

输入样例#2：

3 21 22 3

输出样例#2：

1

说明

【数据规模】

1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。

 

1 /* 2 首先需要认识到图不一定是连通图。因此我们完全可以忽视孤立的点。从1开始枚举点到n， 3 要是没有被研究过并且不是孤立的点的话就对它进行染色。每个连通块之间互不影响， 4 所以我们对于每个连通块累加min{色块1的个数，色块2的个数}即可。 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 using namespace std;10 int n, m, uu, vv, ans1, ans2, ans, shux[10005]={
   0};11 vector
        
             edge[10005];//vector好用 12 bool u[10005];13 void hx(int nl, int sx){
   //当前处在nl点，想染上sx的颜色 14     //我已经染过色了，并且我染的不是sx的颜色 15     if(shux[nl] && shux[nl]!=sx){
   //染糊了 16         cout<<"Impossible";17         exit(0);18     }19     if(shux[nl])    return ;//幽雅地返回吧，染过色的点 20     //已经染色了 21     u[nl] = true;22     //给他染sx色 23     shux[nl] = sx;24     //染的是1号色，ans1++，染的是2号色，ans2++ 25     if(sx==1)    ans1++;26     else             ans2++;27     //对n1相邻的节点染不同的颜色，如果n1染的1号色，周围就染2号色，如果染2号色，周围就染1号色 28     for(int i=0; i
         
          >n>>m;33     for(int i=1; i<=m; i++){34         scanf("%d %d", &uu, &vv);35         edge[uu].push_back(vv);36         edge[vv].push_back(uu);37     }38     for(int i=1; i<=n; i++)39         //u[i]没有被访问过且i不是孤立的点 40         if(!u[i] && edge[i].size()){41             ans1 = ans2 = 0;//累加每种色块个数的变量记得清零 42             //当前处在i点，想染上1的颜色 43             hx(i, 1); 44             //对于不同的联通图，要加上 45             ans += min(ans1, ans2);46         }47     cout<
         
        
       
      
     

 

忘记写16行的cin>>那句话

1 #include 
     
       2 const int M=1e5+10; 3 const int N=1e4+10; 4 using namespace std; 5 int n,m,vis[N]; 6 vector
      
        vct[N]; 7 queue
       
         q; 8 int edgeNum[N]; 9 int num;10 int minNum=0x3fffffff; 11 12 void init(){13     cin>>n>>m;14     for(int i=1;i<=m;i++){15         int u,v;16         cin>>u>>v;//这句话忘记了 17         edgeNum[u]++; 18         vct[u].push_back(v);19         edgeNum[v]++; 20         vct[v].push_back(u); 21     }22 }23 24 bool check(){25     for(int i=1;i<=n;i++){26         if(vis[i]==1){27             for(int j=0;j
        
         n) i1-=n;61             q.push(i1++);62         } 63         memset(vis,0,sizeof(vis));64         num=0;65         search();66     }67 }68 69 void print(){70     if(minNum==0x3fffffff) cout<<"Impossible"<
        
       
      
     

 

1 #include 
     
       2 const int N=1e4+10; 3 using namespace std; 4 int n,m,color[N],ans,ans1,ans2; 5 bool vis[N]; 6 vector
      
        vct[N]; 7  8 void setColor(int p,int type){ 9     if(color[p]&&color[p]!=type){10         cout<<"Impossible"<
       
        >n>>m;25     for(int i=1;i<=m;i++){26         int u,v;27         cin>>u>>v;28         vct[u].push_back(v);29         vct[v].push_back(u);30     }31     for(int i=1;i<=n;i++){32         if(!vis[i]&&!vct[i].empty()){33             ans1=0,ans2=0;34             setColor(i,1);35             ans+=min(ans1,ans2);36         }37     }38     cout<
        
         <