Bus Planning Kattis - busplanning （状压DP）

题目

https://cn.vjudge.net/problem/Kattis-busplanning

题意

给你n个人，有些人有矛盾，给定每个车的容量，问最少多少辆车能装下。

思路

状压DP

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int n,c,k;
string s[18];
int vis[1<<18];
int dp[1<<18];
map<string,int> mp;
int state;
struct node
{int x,y;
}qw[4000];
int init(int x)
{int ans = 0;for(int i = 0;i < n;i++) if((1<<i)&x) ans++;if(ans > c) return inf;for(int i = 0;i < k;i++){int a = qw[i].x,b = qw[i].y;if(((1<<a)&x)&&((1<<b)&x)) return inf;}return 1;
}
void dfs(int x)
{if(dp[x] == 1){for(int i = 0;i < n;i++){if((1<<i)&x) cout<<s[i]<<" ";}cout<<endl;return ;}dfs(x^vis[x]);dfs(vis[x]);
}
int main()
{ios::sync_with_stdio(false);cin>>n>>k>>c;state = 1<<n;for(int i = 0;i < n;i++){cin>>s[i];mp[s[i]] = i;}memset(qw,0,sizeof(mp));string a,b;for(int i =0;i < k;i++){cin>>a>>b;qw[i].x = mp[a];qw[i].y = mp[b];}for(int i = 0;i < state;i++) dp[i] = init(i);for(int i = 0;i < state;i++){for(int j = i;j;j=(j-1)&i){if(dp[i]>dp[i^j]+dp[j]) dp[i] = dp[i^j] + dp[j],vis[i] = j;}}cout<<dp[state-1]<<endl;dfs(state-1);return 0;
}