好长时间没更博客了
因为实在太蒻了
这让本蒟蒻怎么办
今天终于遇到了一道模板题(之前也有,不过太蒻了都不会)
不过...写代码5分钟,调试2小时
分界线:回归正题
这个就是普通的匈牙利算法 差不多
思路:
我们需要统计出谁需要床,谁有床
我们的二分图就是 需要的人 和 床
跑匈牙利就好了
什么人不需要床?? 在校且回家的人
什么床能用?? 在校的人
由于人的序号和床的序号会重复
所以我在床的序号上加了m,(比如一共有3个人,一号床的"名字"就是4)
如果还不明白上面那句那就可以理解为#define 一号床 4
由于题目要求输入是邻接矩阵,所以我们可以只读入一半(左上角和右下角连线以左不读)
因为人的信任是相互的
对应好之后就可以了
做这道题,怎么做?
1 : 学会匈牙利算法,不管你用Google.Baidu.360.搜狗.bing.yandex......什么引擎(能用就行)
都有很生动的例子,这里不再赘述
2 : 学会图论基本知识,会用邻接表存边(只会邻接矩阵的话可以先学一学或者看懂我的之后自己写)
3 : 写代码,就是用你的小爪爪摸一下键盘
4 : debug,dalao自行跳过
5 : 最重要的一步:
打上神兽!!!!
┌─┐ ┌─┐
┌─┘ ┴────┘ ┴─┐
│ │
│ ─── │
│ ─┬┘ └┬─ │
│ │
│ ─┴─ │
│ │
└──┐ ┌──┘
│ │
│ │
│ │
│ │
│ │
│ │
│ │
│ └──────────┐
│ │
│ ├─┐
│ ┌─┘
│ │
└─┐ ┐ ┌────┬ ┐ ┌──┘
│─┤─┤ │─┤─┤
└─┴─┘ └─┴─┘
神兽保佑
代码无BUG!
看起来好像不大对,但是粘贴到记事本或sublime(Dev也行)
就会变成非常帅气的样子
现在贴代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
inline void write(int x) {if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); }
int u[10001],v[10001],f[10001],N[10001],g[10001];
bool bj[10001],bj2[10001],book[10001];
void add(int x,int y,int z){//邻接表存边
u[z] = x; v[z] = y;
N[z] = f[x]; f[x] = z;
}
bool find(int x){//匈牙利模板
for(int i = f[x];i != -1;i = N[i]){
int p = v[i];
if(!book[p]){
book[p] = 1;
if(g[p] == 0 || find(g[p])){
g[p] = x;
return 1;
}
}
}
return 0;
}
int main(int argc, char const *argv[])
{
int yy;
yy = read();
while(yy){
int tt = 0;
yy--;
memset(f,-1,sizeof f);//多测不清空,爆零两行泪
memset(u,0,sizeof u);
memset(v,0,sizeof v);
memset(g,0,sizeof g);
memset(bj,0,sizeof bj);
memset(bj2,0,sizeof bj2);
int m,x,tot = 0;
m = read();
for(int i = 1;i <= m;++i) bj[i] = read();//在校标记
for(int i = 1;i <= m;++i) {
x = read();
bj2[i] = x;//是否回家的标记
if(!bj[i]) bj2[i] = 0;//不在校就可以当不回家处理(因为需要床)
if(bj2[i]) tt++;
}
for(int i = 1;i <= m;++i){
for(int j = 1;j <= m;++j){
x = read();
if(i > j) continue;//只读一半
if(i == j && bj[i])//自己可以睡自己的床
x = 1;
if(x == 0) continue;//不能互相睡床不存边
if(bj[j] && !bj2[i]){//j有床i不回家就加边
// cout<<i<<" "<<j<<endl;
add(i,m + j,++tot);
}
if(i == j) continue;
if(bj[i] && !bj2[j]){//同理
// cout<<j<<" "<<i<<endl;
add(j,m + i,++tot);
}
}
}
// for(int i = 1;i <= m;++i){
// cout<<f[i]<<" "<<N[i]<<endl;
// }
int cnt = 0;
for(int i = 1;i <= m;++i){
memset(book,0,sizeof book);
if(find(i)) cnt++;
}
if(cnt == m - tt) cout<<"^_^"<<"
";
else cout<<"T_T"<<"
";
}
return 0;
}
/***
* ┌─┐ ┌─┐
* ┌─┘ ┴────┘ ┴─┐
* │ │
* │ ─── │
* │ ─┬┘ └┬─ │
* │ │
* │ ─┴─ │
* │ │
* └──┐ ┌──┘
* │ │
* │ │
* │ │
* │ │
* │ │
* │ │
* │ │
* │ └──────────┐
* │ │
* │ ├─┐
* │ ┌─┘
* │ │
* └─┐ ┐ ┌────┬ ┐ ┌──┘
* │─┤─┤ │─┤─┤
* └─┴─┘ └─┴─┘
* 神兽保佑
* 代码无BUG!
*/