NC14122. ACM Battle
描述
输入描述
第一行包含一个正整数T(≤ 20)，表示测试数据的组数，
对于每组测试数据，
第一行是两个整数n(1 ≤ n ≤ 1000)和m(1 ≤ m ≤ 2000)，表示魔法阵的点数和边数，
接下来m行，每行包含两个整数u,v(1 ≤ u,v ≤ n)，表示有一条边连接了u号点和v号点。
输出描述
对于每组测试数据，如果使用不超过10滴圣水可以点亮整个魔法阵，输出最少需要的圣水滴数，否则输出"GG"（不含引号）。
示例1
输入:
2 4 3 1 2 1 3 1 4 4 4 1 2 2 3 3 4 4 1
输出:
1 2
说明:
对于第一组样例，最优方案是在1号点滴一滴圣水，C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 688K, 提交时间: 2020-07-05 20:27:04
#include<bits/stdc++.h>
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N=2e3+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
int T,n,m,ans,v[N];
struct Node{
int l,r;
}edge[N];
void dfs(int x,int p){
if(p>=ans)return;
if(x==m+1){
ans=min(ans,p);
return;
}
if(v[edge[x].l] || v[edge[x].r])dfs(x+1,p);
else{
v[edge[x].l]=1;
dfs(x+1,p+1);
v[edge[x].l]=0;
v[edge[x].r]=1;
dfs(x+1,p+1);
v[edge[x].r]=0;
}
}
int main(){
Fox;
cin>>T;
while(T--){
cin>>n>>m;
ans=11;memset(v,0,sizeof(v));
for(int i=1;i<=m;i++)cin>>edge[i].l>>edge[i].r;
dfs(1,0);
if(ans<=10)cout<<ans<<"\n";
else cout<<"GG\n";
}
return 0;
}
C++(clang++11) 解法, 执行用时: 20ms, 内存消耗: 384K, 提交时间: 2021-02-25 10:45:22
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int n,m,vis[N],u[N],v[N],ans;
void dfs(int x,int cnt){
if(cnt>10||cnt>ans) return ;
if(x==m+1){ans=min(ans,cnt); return ;}
if(vis[u[x]]||vis[v[x]]) dfs(x+1,cnt);
else{
vis[u[x]]=1,dfs(x+1,cnt+1),vis[u[x]]=0;
vis[v[x]]=1,dfs(x+1,cnt+1),vis[v[x]]=0;
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>u[i]>>v[i];
ans=1e9; dfs(1,0);
if(ans==1e9) puts("GG");
else printf("%d\n",ans);
}
int main(){
int T; cin>>T; while(T--) solve();
return 0;
}