UVa 1627 Team them up! (01背包+二分图)
2024-09-03 22:30:27
题意:给n个分成两个组,保证每个组的人都相互认识,并且两组人数相差最少,给出一种方案。
析:首先我们可以知道如果某两个人不认识,那么他们肯定在不同的分组中,所以我们可以根据这个结论构造成一个图,如果两个不相互认识,
那么就加一条边,然后如果这个图是二分图,那么这分组是可以,否则就是不可能的。然后dp[i][j]表示那两个组相差人数为 j 是不是可以达到,
当然可能为负数,所以可以提前加上n,然后就是逆序输出答案即可。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#define debug() puts("++++");
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std; typedef long long LL;
typedef unsigned long long ULL;
typedef pair<double, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-5;
const int maxn = 100 + 10;
const int mod = 1e6;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
int color[maxn];
bool g[maxn][maxn];
vector<int> v[maxn][2];
int diff[maxn], cnt;
bool dp[maxn][maxn*2]; bool dfs(int u, int val){
color[u] = val;
v[cnt][val-1].push_back(u);
for(int i = 1; i <= n; ++i){
if(i == u) continue;
if(g[u][i] && g[i][u]) continue;
if(color[i] == color[u]) return false;
if(!color[i] && !dfs(i, 3-val)) return false;
}
return true;
} void print(int ans){
vector<int> v1, v2;
for(int i = cnt-1; i >= 0; --i){
int t;
if(dp[i][ans+n+diff[i]]){ t = 0; ans += diff[i]; }
else { t = 1; ans -= diff[i]; }
for(int j = 0; j < v[i][t].size(); ++j)
v1.push_back(v[i][t][j]);
for(int j = 0; j < v[i][t^1].size(); ++j)
v2.push_back(v[i][t^1][j]);
}
printf("%d", v1.size());
for(int i = 0; i < v1.size(); ++i) printf(" %d", v1[i]);
printf("\n");
printf("%d", v2.size());
for(int i = 0; i < v2.size(); ++i) printf(" %d", v2[i]);
printf("\n");
} void solve(){
memset(dp, 0, sizeof dp);
dp[0][n] = true;
for(int i = 0; i < cnt; ++i){
for(int j = -n; j <= n; ++j) if(dp[i][j+n]){
dp[i+1][j+n+diff[i]] = true;
dp[i+1][j+n-diff[i]] = true;
}
}
for(int i = 0; i <= n; ++i){
if(dp[cnt][i+n]){ print(i); return ; }
if(dp[cnt][-i+n]){ print(-i); return ; }
}
} int main(){
int T; cin >> T;
while(T--){
scanf("%d", &n);
memset(g, 0, sizeof g);
for(int i = 1; i <= n; ++i){
while(scanf("%d", &m) == 1 && m) g[i][m] = true;
}
memset(color, 0, sizeof color);
bool ok = true;
cnt = 0;
for(int i = 1; i <= n && ok; ++i) if(!color[i]){
v[cnt][0].clear();
v[cnt][1].clear();
ok = dfs(i, 1);
diff[cnt] = (int)v[cnt][0].size() - v[cnt][1].size();
++cnt;
}
if(!ok) puts("No solution");
else solve();
if(T) printf("\n");
}
return 0;
}
最新文章
- 获取youku视频下载链接(wireshark抓包分析)
- Android 自定义View (五)&mdash;&mdash;实践
- android MediaPlayer API大全已经方法详解(转载)
- 前端测试回顾及我们为什么选择Karma
- spring.net中的IOC和DI-初使用
- Spring中使用Jcaptcha实现校验码验证
- obj-c 坑
- git for windows+TortoiseGit客户端的使用二
- HDU 5067 Harry And Dig Machine:TSP(旅行商)
- UWP 手绘视频创作工具技术分享系列 - 手绘视频导出
- java.sql.SQLException之数组越界
- 代码的重构(Refactor-Extract)
- HTTP 2.0 原理详细分析
- 关于scanf、getchar、getch、getche缓冲区分析——C语言
- 理解REST和SOA
- 不用U盘,用一台好电脑给另一个电脑重装windows10
- 如何在Maven和Gradle中配置使用Groovy 2.4与Spock 1.0
- cxf之Caused by: java.lang.RuntimeException: Soap 1.1 endpoint already registered on address /rest
- PIL图片合成旋转缩放
- 【医学影像】《Dermatologist-level classification of skin cancer with deep neural networks》论文笔记