【CDOJ 79】Playground

题目传送门:http://www.acm.uestc.edu.cn/#/problem/show/79
数据生成器:http://paste.ubuntu.com/18848244/

这个题,并查集搞一搞就过了。
然而后来得知一种二分图匹配的思路,感觉很科学,叉不掉。于是写了写代码。
最后发现,二分图匹配的话,只能保证在满足限制的情况下,得出最少解,并不能保证全部染完,比如十字架

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 500;

int fa[MAXN],n,tag[MAXN],vout,que[MAXN],mat[MAXN][MAXN];

inline int find(int w){
	int f=fa[w], tmp;
	while (f != fa[f]) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

inline void connect(int a, int b){
	int f1 = find(a), f2 = find(b);
	if (f2 != f1) fa[f2] = f1;
}	

inline void solve(int sta){
	int tot = 0, ret = 0;
	for (int i=1;i<=n*2;i++)
		if (fa[i] == sta)
			que[++tot] = i;
	for (int i=1;i<=tot;i++) if (tag[que[i]]){
		int w = que[i]; ret++;
		if (w <= n){ 
			for (int j=1;j<=n;j++)
				if (mat[w][j]) tag[n+j] = 0;
		} else {
			for (int j=1;j<=n;j++)
				if (mat[j][w-n]) tag[j] = 0;
		}
	}
	vout += min(ret, tot-ret);
}

int main(){
	int T; cin>>T;
	while (T--){
		scanf("%d",&n); vout = 0;
		for (int i=1;i<=2*n;i++) fa[i] = i;
		for (int j=1,tmp;j<=n;j++){
			for (int i=1;i<=n;i++){
				scanf("%d",&tmp);
				mat[i][j] = tmp;
				if (tmp == 1) 
					connect(i,j+n), 
					tag[i] = tag[j+n] = 1;
			}
		}	
		for (int i=1;i<=n*2;i++) fa[i] = find(i);
		for (int i=1;i<=n*2;i++) if (fa[i]==i & tag[i])
			solve(fa[i]);
		printf("%d\n",vout);
	}	
	return 0;
} 

23 thoughts to “【CDOJ 79】Playground”

  1. You are so awesome! I do not suppose I’ve truly read something
    like this before. So great to find another person with original
    thoughts on this subject matter. Seriously.. thanks for starting this
    up. This website is one thing that is needed on the internet, someone with a bit of originality!

  2. Awesome blog! Is your theme custom made or did you download it from somewhere?
    A design like yours with a few simple tweeks would really make my blog jump out.
    Please let me know where you got your theme. Appreciate
    it

  3. Hi, Neat post. There’s an issue along with your site in internet explorer, may test
    this? IE nonetheless is the market chief and a good part of folks
    will leave out your magnificent writing because of this problem.

  4. I truly love your site.. Very nice colors & theme. Did you build this amazing site
    yourself? Please reply back as I’m trying to create my own website and would like to learn where you got this from or
    exactly what the theme is named. Appreciate it!

  5. Hi there! I realize this is kind of off-topic but I needed to ask.
    Does running a well-established website such as yours require a massive amount
    work? I’m brand new to writing a blog however I do write in my journal everyday.
    I’d like to start a blog so I can easily share
    my experience and thoughts online. Please let me know if you have
    any kind of ideas or tips for new aspiring bloggers.
    Thankyou!

  6. Great web site you have got here.. It’s difficult to find good
    quality writing like yours nowadays. I truly appreciate
    individuals like you! Take care!!

  7. I’m not sure why but this blog is loading incredibly slow for me.
    Is anyone else having this issue or is it a issue on my end?
    I’ll check back later and see if the problem still exists.

  8. You can definitely see your skills within the work you write.
    The sector hopes for even more passionate writers like you who are not afraid
    to say how they believe. All the time go after your heart.

  9. I was wondering if you ever considered changing the
    structure of your website? Its very well written; I love what youve got to say.

    But maybe you could a little more in the way of content
    so people could connect with it better. Youve got an awful lot of text for only having one or 2 pictures.

    Maybe you could space it out better?

  10. My developer is trying to persuade me to move to .net from PHP.
    I have always disliked the idea because of the costs.

    But he’s tryiong none the less. I’ve been using Movable-type
    on a number of websites for about a year and am anxious about
    switching to another platform. I have heard excellent things about blogengine.net.
    Is there a way I can import all my wordpress posts into it?
    Any help would be greatly appreciated!

  11. Hello there, I found your web site via Google whilst
    searching for a comparable subject, your web site got here up, it seems good.
    I have bookmarked it in my google bookmarks.
    Hi there, just was aware of your blog through Google, and located that it’s truly informative.
    I am going to be careful for brussels. I will be grateful if you continue this in future.

    Many other people can be benefited out of your writing. Cheers!

Leave a Reply

Your email address will not be published. Required fields are marked *