题目大意
给定$n(n \le 300)$个外星人，给定$m(m \le 1500)$个地球人，再给定任意地球人与外星人的关系
关系由一个$nm$的0/1矩阵给出，表示第$i$个外星人是否能与第$j$个地球人配对
要求每个外星人至少与一个地球人配对，地球人只能与至多一个外星人匹配
问由哪些关系一定不可能出现在合法的匹配方案中
解题报告
这是一道基础图论题
我们可以先来考虑一个简单的版本：地球人个数与外星人一样
那么我们可以先用二分图匹配跑一个完备匹配出来
此时在匹配中的边一定可以出现在合法的匹配方案中
只考虑不在当前匹配中的边，那么一定是走一条像增广路一样的东西
就是一条匹配边，一条非匹配边交叉着走。最后走一个偶环绕回来
于是我们对于从左边连到右边的边，只保留非匹配边
对于从右到左的边，我们只保留匹配边。这样就可以保证是偶环了
至于能不能走回来，我们发现这就是一个有向图的强连通分量
于是我们再跑一个Tarjan，判断一下就可以了
现在考虑地球人与外星人不等的情况
我们可以把外星人补到与地球人一样多啊！
就是加一些可以与所有地球人匹配的外星人就可以了
当然不加点，大力讨论一波也是可以的
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3009;
const int M = N * N << 1;
const int INF = 1e9;
int head[N],nxt[M],to[M],flow[M],low[N],dfs[N];
int n,m,S,T,E=1,mth[N],id[N][N],num[N],ins[N]; char pat[N];
stack<int> stk;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline int AddEdge(int u, int v, int f=0) {
if (f) {
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u, nxt[E] = head[v], head[v] = E;
flow[E - 1] = f; return E - 1;
} else to[++E] = v, nxt[E] = head[u], head[u] = E;
}
class Network_Flow{
int dis[N],cur[N]; queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
memcpy(cur,head,sizeof(cur));
ret += DFS(S, INF);
} return ret;
}
private:
int DFS(int w, int f) {
if (w == T) return f; int ret = 0;
for (int &i=cur[w],tmp;i;i=nxt[i]) {
if (flow[i] && dis[to[i]] == dis[w] + 1) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) return ret;
}
} return ret;
}
inline bool BFS() {
memset(dis,60,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) {
if (flow[i] && dis[to[i]] > INF) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
} return dis[T] < INF;
}
}Dinic;
void Tarjan(int w) {
static int dfs_cnt = 0, scc_cnt = 0;
dfs[w] = low[w] = ++dfs_cnt; stk.push(w); ins[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
if (!dfs[to[i]]) Tarjan(to[i]), low[w] = min(low[w], low[to[i]]);
else if (ins[to[i]]) low[w] = min(low[w], dfs[to[i]]);
}
if (low[w] == dfs[w]) {
for (scc_cnt++;!stk.empty();stk.pop()) {
num[stk.top()] = scc_cnt; ins[stk.top()] = 0;
if (stk.top() == w) {stk.pop(); break;}
}
}
}
int main() {
n = read(); m = read(); S = 0; T = N - 1;
memset(id, -1, sizeof(id));
for (int i=1;i<=n;i++) {
scanf("%s",pat+1);
for (int j=1;j<=m;j++) {
if (pat[j] == '1') {
id[i][j] = AddEdge(i, m + j, 1);
}
}
}
for (int i=1;i<=n;i++) AddEdge(S, i, 1);
for (int i=1;i<=m;i++) AddEdge(m + i, T, 1);
if (Dinic.MaxFlow() != n) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) putchar('1');
puts("");
}
} else {
E = 1; memset(head,0,sizeof(head));
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if (~id[i][j] && !flow[id[i][j]]) {mth[j] = i; break;}
for (int i=n+1,j=1;i<=m;i++,j++) {while(mth[j])j++;mth[j]=i;}
for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) if (~id[i][j] || i > n) {
if (mth[j] == i) AddEdge(m+j, i); else AddEdge(i, m+j);}
for (int i=1;i<=m*2;i++) if (!dfs[i]) Tarjan(i);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if ((~id[i][j]) && (mth[j] == i || num[i] == num[m+j])) putchar('0');
else putchar('1');
} putchar('\n');
}
}
return 0;
}
哇塞，居然是沙发？留个名
Having read this I thought it was really informative.
I appreciate you finding the time and energy to
put this content together. I once again find myself
spending way too much time both reading and leaving comments.
But so what, it was still worth it!
Right away I am going to do my breakfast, once having my breakfast coming again to read more news.
This is really interesting, You’re a very skilled blogger. I’ve joined your feed
and look forward to seeking more of your excellent post.
Also, I have shared your website in my social networks!
Ahaa, its pleasant conversation regarding this post at this place at this website,
I have read all that, so now me also commenting here.
Hey! Quick question that’s totally off topic. Do you know how to make your site mobile
friendly? My website looks weird when browsing from my
iphone. I’m trying to find a template or plugin that might be
able to fix this problem. If you have any suggestions,
please share. Many thanks!
Thank you for the auspicious writeup. It in reality used to be a entertainment account it.
Look advanced to far introduced agreeable from you!
By the way, how could we keep in touch?
Does your website have a contact page? I’m having trouble locating it but, I’d like to send
you an email. I’ve got some suggestions for your blog you might be interested in hearing.
Either way, great site and I look forward to seeing it develop
over time.
This post will help the internet people for building up new website or even a blog from
start to end.
Right now it sounds like Drupal is the best blogging platform available right now.
(from what I’ve read) Is that what you’re using on your blog?
certainly like your website however you need to take a look at the spelling on quite a few of your posts.
Several of them are rife with spelling problems and I find it very troublesome to inform the reality however I will certainly come again again.
It is perfect time to make some plans for the future and it is time to be happy.
I’ve read this post and if I could I wish to suggest you some interesting things
or tips. Perhaps you could write next articles referring
to this article. I want to read even more things about it!
It’s perfect time to make some plans for the future and it’s time to be happy.
I have read this post and if I could I wish to suggest you
few interesting things or suggestions. Perhaps you can write next articles referring to this article.
I wish to read even more things about it!
I like what you guys are up too. Such smart work and reporting! Carry on the excellent works guys I’ve incorporated you guys to my blogroll. I think it will improve the value of my website :).
Hello there! Do you know if they make any plugins to assist with Search Engine Optimization? I’m trying to get my
blog to rank for some targeted keywords but I’m not seeing very good success.
If you know of any please share. Kudos!
Hey There. I found your blog using msn. This is
an extremely well written article. I will make sure to bookmark it and come back to
read more of your useful info. Thanks for the post.
I will certainly comeback.
Very nice article, just what I was looking for.
I’m impressed, I must say. Rarely do I encounter a blog that’s both equally educative and amusing, and
let me tell you, you’ve hit the nail on the head.
The problem is something that not enough people are speaking intelligently about.
I am very happy I stumbled across this in my search for something relating to this.
I do agree with all of the ideas you have introduced to
your post. They’re really convincing and will definitely work.
Nonetheless, the posts are too brief for beginners.
May you please prolong them a little from next time?
Thanks for the post.
Great website. Lots of helpful information here. I’m sending it to a few pals ans additionally sharing in delicious. And naturally, thank you for your sweat!