Vertex Cover
| frog has a graph with nn vertices v(1),v(2),…,v(n)v(1),v(2),…,v(n) and mm edges (v(a1),v(b1)),(v(a2),v(b2)),…,(v(am),v(bm))(v(a1),v(b1)),(v(a2),v(b2)),…,(v(am),v(bm)). She would like to color some vertices so that each edge has at least one colored vertex. Find the minimum number of colored vertices. |
Input
| The input consists of multiple tests. For each test: The first line contains 22 integers n,mn,m (2≤n≤500,1≤m≤n(n?1)22≤n≤500,1≤m≤n(n?1)2). Each of the following mm lines contains 22 integers ai,biai,bi (1≤ai,bi≤n,ai≠bi,min{ai,bi}≤301≤ai,bi≤n,ai≠bi,min{ai,bi}≤30) |
Output
| For each test, write 11 integer which denotes the minimum number of colored vertices. |
Sample Input
| 3 2 1 2 1 3 6 5 1 2 1 3 1 4 2 5 2 6 |
Sample Output
| 1 2 |
题意：有n个点（n<=500），m条边，所有大于30的点都会与前30中的一个相连。。然后给出所有相连的点，求染多少次能让所有的点都染上
爆搜到30就行了
爆搜+减zhi（感觉也没咋减）。。。
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<set>
using namespace std;
#define inf 0x3f3f3f3f
vector<int>q[510];
int n,m;
int max_ran;
int ans;
int vis[510];
void dfs(int k,int sum)
{ if(sum>ans) return;if(k>max_ran){ans=sum;return;}if(vis[k]) dfs(k+1,sum);else{vis[k]++;dfs(k+1,sum+1);vis[k]--;int size=q[k].size();for(int i=0;i<size;i++){if(!vis[q[k][i]])sum++; vis[q[k][i]]++;}dfs(k+1,sum);for(int i=0;i<size;i++){vis[q[k][i]]--;if(!vis[q[k][i]])sum--; }}
}
int main()
{while(cin>>n>>m){ for(int i=0;i<=n;i++)q[i].clear();for(int i=0;i<m;i++){int u,v;cin>>u>>v;q[u].push_back(v);q[v].push_back(u);}ans=inf;max_ran=min(n,30);memset(vis,0,sizeof(vis));dfs(1,0);cout<<ans<<endl;}return 0;
}