Bowls and Dishes
題意：
- 給你n個dish，有m個條件，
- 一個條件要成立，那么它要兩個給定的dish中有球，
- 現在又k個人，每個人可以選擇一個dish然后放球，且每個人有兩個選擇，
- 問：怎樣可以使得 m個條件盡量成立，
思路：
- 資料小，可以考慮直接暴搜，
- bitmsks 每一位的0（1）代表選第一個dish，還是第二個dish，
AC
#include <iostream>
#include <bits/stdc++.h>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define fori(i,x,y) for(int i=(x); i<(y); i++)
#define rep(i,y,x) for(int i=(y); i>=(x); i--)
#define mst(x,a) memset(x,a,sizeof(x))
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define fi first
#define se second
#define debug(a) cout << #a << ": " << a << endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pa;
typedef pair<ll,ll>pai;
const int N = 2e5+10;
const int M = 1e5;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m, k;
cin>>n>>m;
vector<int>a(m),b(m);
// vector<vector<int> > c(vector<int>(2),2);
//ctor<>
int u, v;
for(int i = 0; i < m; i ++ ){
cin>>a[i]>>b[i];
a[i]--,b[i]--;
}
cin>>k;
vector<int>c(k),d(k);
for(int i = 0; i < k ; i ++ ){
cin>>c[i]>>d[i];
c[i]--,d[i]--;
}
int ans = 0;
for(int bitmasks =0; bitmasks< (1<<k); bitmasks ++ ){
vector<int>vis(n);
for(int i = 0; i <k; i ++ ){
if((bitmasks>>i)&1)vis[c[i]] = 1;
else vis[d[i]] = 1;
}
int sum = 0;
for(int i = 0; i < m ; i ++ ){
if(vis[a[i]]&&vis[b[i]])sum++;
}
ans= max(ans,sum);
}
cout<<ans<<'\n';
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255304.html
標籤：其他
上一篇：第八屆“圖靈杯”NEUQ-ACM程式設計競賽（全題解&&詳細）
下一篇：蛇形矩陣，蛇皮走位~