给出n个点,m条边,每个点能控制与其相连的所有的边,要求选出一些点,使得这些点能控制所有的边,并且点数最少。同时,任意一条边不能被两个点控制
输入格式:
第一行给出两个正整数n,m
第2~m+1行,描述m条无向边
每行给出x,y,表示一条无向边(x,y)
输出格式:
输出最少需要选择的点的个数,如果无解输出“Impossible”(不带引号)
输入样例#1:
7 5
1 2
1 3
5 6
6 7
1 2
输出样例#1:
2
【数据范围】
对于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 }