【BZOJ4155】[Ipsc2015]Humble Captains 最小割+DP
最小 DP
2023-09-11 14:15:24 时间
【BZOJ4155】[Ipsc2015]Humble Captains
Description
每天下午放学时都有n个zky冲出教室去搞基。搞基的zky们分成两队,编号为1的zky是1号队的首领,编号为2的zky是2号队的首领。其他的zky可以自由选择是去1队还是2队。
zky们当中有几对zky是好基友(同一个zky可能在多对“好基友”关系中),如果一对好基友在同一个队,那么这个队的战斗力就+1。
现在你要解决两个问题:1.两队战斗力之和最大是多少?2.两队战斗力之差的绝对值最小是多少?
注意:这两个问题是不相关的。也就是说,问1和问2的方案可以是不一样的。
Input
第一行t表示数据组数
每一组测试数据的第一行包含两个整数n,m,zky们编号从1到n,共有m对好基友关系。
接下来m行每行两个整数u和v,表示u和v之间存在好基友关系。保证每一对好基友关系只会被描述一次。
Output
对每一组,输出一行两个数,第一个是最大战斗力之和,第二个是最小战斗力之差。
Sample Input
2
3 3
1 2
2 3
1 3
3 1
1 3
3 3
1 2
2 3
1 3
3 1
1 3
Sample Output
1 1
1 0
1 0
HINT
n <= 200, t <= 250
题解:第一问不会的去练最小割,第二问不会的去做阿狸和桃子的游戏。
然而本题第二问求的是差最小,那么把贪心换成 搭建双塔 即可。
但是复杂度有点高,用bitset优化即可。
#include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <bitset> using namespace std; int n,m,T,cnt,ans; int pa[300],pb[300],to[100000],next[100000],val[100000],head[300],d[300],D[300]; bitset<80010> f; queue<int> q; inline void add(int a,int b) { to[cnt]=b,val[cnt]=1,next[cnt]=head[a],head[a]=cnt++; to[cnt]=a,val[cnt]=1,next[cnt]=head[b],head[b]=cnt++; } int dfs(int x,int mf) { if(x==2) return mf; int i,temp=mf,k; for(i=head[x];i!=-1;i=next[i]) if(d[to[i]]==d[x]+1&&val[i]) { k=dfs(to[i],min(temp,val[i])); if(!k) d[to[i]]=0; val[i]-=k,val[i^1]+=k,temp-=k; if(!temp) break; } return mf-temp; } inline int bfs() { memset(d,0,sizeof(d)); while(!q.empty()) q.pop(); int i,u; d[1]=1,q.push(1); while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i!=-1;i=next[i]) if(!d[to[i]]&&val[i]) { d[to[i]]=d[u]+1; if(to[i]==2) return 1; q.push(to[i]); } } return 0; } inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } void work() { n=rd(),m=rd(),ans=0; int i,a,b; memset(head,-1,sizeof(head)),memset(D,0,sizeof(D)),cnt=0; for(i=1;i<=m;i++) a=rd(),b=rd(),add(a,b),D[a]++,D[b]++; while(bfs()) ans+=dfs(1,1<<30); printf("%d ",m-ans); f.reset(),f[n*n+D[1]-D[2]]=1; for(i=3;i<=n;i++) f=(f<<D[i])|(f>>D[i]); for(i=0;i<=n*n;i++) if(f[n*n+i]||f[n*n-i]) { printf("%d\n",i>>1); return ; } } int main() { T=rd(); while(T--) work(); return 0; }
相关文章
- poj3422 Kaka's Matrix Travels(最小费用最大流问题)
- 【方法3:Perl版本】删除Map中Value重复的记录,并且只保留Key最小的那条记录
- Java实现 LeetCode 801 使序列递增的最小交换次数 (DP)
- Java实现 LeetCode 801 使序列递增的最小交换次数 (DP)
- Java实现 蓝桥杯 算法训练 最大最小公倍数
- 【数组&双指针】LeetCode 76. 最小覆盖子串【困难】
- 基于移动最小二乘的图像变形和曲线拟合
- LeetCode-1769. 移动所有球到每个盒子所需的最小操作数【数组,前缀和】
- 5、spss做加权最小二乘回归及岭回归
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-201 大等于n的最小完全平方数
- 习题 5.7 找出一个二维数组中的鞍点,即该位置上的元素在该行上最大,在该列上最小(也可能没有鞍点)。
- 2-2 畅通工程之局部最小花费问题
- 一个点的经度和纬度,以这个点为圆心,1000米为半径,最大的经度和纬度,最小的经度和纬度
- 【基础知识】~ 时序约束、静态/动态时序分析、DMA、逻辑电平、逻辑最小项、乒乓 buffer、门控时钟、BRAM/DRAM、功耗问题、设计描述方式、延迟设计、DDR 带宽计算
- HDU 3157 Crazy Circuits(有源汇上下界最小流)
- POJ 3422 Kaka's Matrix Travels (最小费用最大流)
- POJ训练计划3041_Asteroids(二分图/最小点覆盖=最大匹配)
- 交替最小二乘ALS
- TR-thread-最小工程的搭建
- 最小二乘法 回归分析中的最小二乘法 最小二乘法(least sqaure method)