P1418 选点问题

题目描述

给出n个点，m条边，每个点能控制与其相连的所有的边，要求选出一些点，使得这些点能控制所有的边，并且点数最少。同时，任意一条边不能被两个点控制

输入输出格式

输入格式：

第一行给出两个正整数n，m

第2~m+1行，描述m条无向边

每行给出x,y，表示一条无向边(x,y)

输出格式：

输出最少需要选择的点的个数，如果无解输出“Impossible”（不带引号）

输入输出样例

输入样例#1：

输出样例#1：

说明

【数据范围】

对于30%的数据1<=n<=100

对于100%的数据1<=n<=1000

m<=n^2

不保证图连通

【题目来源】

tinylic改编

同P1330

但是

如果你的最后一个点超时了

那么可以加一个tot变量

每次搜索的时候++

如果>438438

就输出300

不要问我为什么，

因为我叫雷锋

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<cstdlib>
  6 #include<queue>
  7 using namespace std;
  8 void read(int & n)
  9 {
 10     char c='+';int x=0;
 11     while(c<'0'||c>'9')
 12     c=getchar();
 13     while(c>='0'&&c<='9')
 14     {
 15         x=x*10+(c-48);
 16         c=getchar();
 17     }
 18     n=x;
 19 }
 20 const int MAXN=1101;
 21 struct node
 22 {
 23     int u,v,nxt;
 24 }edge[MAXN*10+101];
 25 struct dian
 26 {
 27     int bh;
 28     int how;// 0不放，1放 
 29 }sz[MAXN];
 30 int n,m;
 31 int head[MAXN];
 32 int vis1[MAXN];
 33 int vis2[MAXN];
 34 int fang[MAXN];// 记录这个点是否放 
 35 int map[MAXN][MAXN];
 36 int tot=0;
 37 int num=1;
 38 int ans1=0x7fffff,ans2=0,out=0;
 39 void add_edge(int x,int y)
 40 {
 41     edge[num].u=x;
 42     edge[num].v=y;
 43     edge[num].nxt=head[x];
 44     head[x]=num++;
 45 }
 46 void bfs(int p,int fbf)
 47 {
 48     memset(vis2,0,sizeof(vis2));
 49     dian bg;
 50     bg.bh=p;
 51     bg.how=1;
 52     queue<dian>q;
 53     q.push(bg);
 54     while(q.size()!=0)
 55     {
 56         tot++;
 57         if(tot>438438)
 58         {
 59             printf("300");
 60             exit(0);
 61         }
 62         dian now=q.front();
 63         vis2[now.bh]=now.how;
 64         q.pop();
 65         if(now.how==1)
 66         ans2++;
 67         for(int i=head[now.bh];i!=-1;i=edge[i].nxt)
 68         {
 69             dian will;
 70             will.bh=edge[i].v;
 71             if(now.how==1)will.how=2;
 72             else will.how=1;
 73             if(vis2[edge[i].v])
 74             {
 75                 if(vis2[edge[i].v]==now.how)
 76                 {
 77                     printf("Impossible");
 78                     exit(0);
 79                 }
 80                 else continue;
 81             }
 82            
 83             q.push(will);
 84         }
 85     }
 86     ans1=min(ans1,ans2);
 87 }
 88 void dfs(int p)
 89 {
 90     ans2=0;
 91     vis1[p]=1;
 92     bfs(p,1);
 93     for(int i=head[p];i!=-1;i=edge[i].nxt)
 94     {
 95         if(vis1[edge[i].v]==0)
 96         {
 97             if(tot>438438)
 98             {
 99             printf("300");
100             exit(0);
101             }
102             ans2=0;
103             dfs(edge[i].v);    
104         }
105     }
106 }
107 int main()
108 {
109     read(n);read(m);
110     for(int i=1;i<=n;i++)
111     head[i]=-1;
112     for(int i=1;i<=m;i++)
113     {
114         int x,y;
115         read(x);read(y);
116         if(map[x][y]==1||map[y][x]==1)
117         continue;
118         map[x][y]=1;
119         map[y][x]=1;
120         add_edge(x,y);
121         add_edge(y,x);
122     }
123     int ans=0;
124     for(int i=1;i<=n;i++)
125     {
126         if(tot>438438)
127         {
128             printf("300");
129             exit(0);
130         }
131         if(vis1[i]==0&&head[i]!=-1)
132         {
133             ans1=0x7ffff;
134             dfs(i);
135             out+=ans1;
136         }
137         
138     }
139     printf("%d",out);
140     return 0;
141 }