目录
BZOJ 4155 Humble Captains题意题解Code
BZOJ 4155 Humble Captains
题目传送门1
题意
每天下午放学时都有n个zky冲出教室去搞基。搞基的zky们分成两队，编号为1的zky是1号队的首领，编号为2的zky是2号队的首领。其他的zky可以自由选择是去1队还是2队。zky们当中有m对zky是好基友（同一个zky可能在多对“好基友”关系中），如果一对好基友在同一个队，那么这个队的战斗力就+1。 现在你要解决两个问题：1.两队战斗力之和最大是多少？2.两队战斗力之差的绝对值最小是多少？ 注意：这两个问题是不相关的。也就是说，问1和问2的方案可以是不一样的。\((1 \leq n \leq 200,1 \leq t \leq 250)\)，\(t\)为数据组数。
题解
这道题一共两个问，实际上就是两道题目综合起来，第一问就是比较裸的最小割，跑一边最大流即可，第二问就和 阿狸和桃子的游戏 很像了，不过是要求差值的最小值，所以就不是贪心地去选了，而是进行\(Dp\)，获得最优的方案，可以用\(bitset\)进行优化。还有，别忘记把边数开大，题目中没有给出\(m\)的大小，所以这可能是达到\(n^2\)级别的。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int N=600;
const int M=1e5+500;
int n,m,T,tot=1;
struct edge {
int to,nxt,w;
}E[M];
int head[N],dis[N],d[N];
bitset<50000>f;
/*==================Define Area================*/
void addedge(int u,int v,int w) {
E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;E[tot].w=w;
E[++tot].to=u;E[tot].nxt=head[v];head[v]=tot;E[tot].w=0;
}
int Bfs() {
memset(dis,-1,sizeof dis);
queue<int>Q;
Q.push(1);
dis[1]=0;
while(!Q.empty()) {
int o=Q.front();Q.pop();
for(int i=head[o];~i;i=E[i].nxt) {
int to=E[i].to;
if(dis[to]==-1&&E[i].w) {
dis[to]=dis[o]+1;
Q.push(to);
}
}
}
return dis[2]!=-1;
}
int Dfs(int u,int flow) {
if(u==2) return flow;
int used=0,k;
for(int i=head[u];~i;i=E[i].nxt) {
int to=E[i].to;
if(dis[to]==dis[u]+1&&E[i].w) {
k=Dfs(to,min(E[i].w,flow-used));
E[i].w-=k;E[i^1].w+=k;
used+=k;
if(used==flow) return flow;
}
}
if(!used) dis[u]=-1;
return used;
}
int main() {
read(T);
while(T--) {
memset(head,-1,sizeof head);tot=1;
memset(d,0,sizeof d);
read(n);read(m);
int ans=m;
for(int i=1,u,v;i<=m;i++) {
read(u);read(v);
addedge(u,v,1);
addedge(v,u,1);
d[u]++;d[v]++;
}
while(Bfs()) ans-=Dfs(1,0x3f3f3f3f);
printf("%d ",ans);
f.reset();
f[n*n+d[1]-d[2]]=1;
for(int i=3;i<=n;i++) f=(f<<d[i])|(f>>d[i]);
for(int i=0;i<=n*n;i++) {
if(f[i+n*n]||f[n*n-i]) {printf("%d\n",i/2);break;}
}
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9582284.html
相关资源：JAVA上百实例源码以及开源项目
