题目传送门: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; }
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!
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
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.
What a material of un-ambiguity and preserveness of precious know-how about unpredicted emotions.
Thanks very nice blog!
It’s really a cool and useful piece of info. I’m happy
that you shared this helpful information with us. Please keep us up to date like this.
Thank you for sharing.
Highly energetic blog, I loved that bit. Will there be
a part 2?
Hi to all, it’s in fact a fastidious for me to pay
a visit this website, it consists of priceless Information.
I have read so many articles regarding the blogger lovers
however this article is really a fastidious article,
keep it up.
I really like it when folks come together and share
views. Great website, stick with it!
Wonderful website. Plenty of useful info here. I am sending it to several pals ans also sharing
in delicious. And certainly, thank you on your sweat!
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!
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!
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!!
This information is worth everyone’s attention. How can I find out more?
I pay a quick visit everyday some sites and
information sites to read content, however this weblog provides quality based writing.
Hello, i think that i saw you visited my weblog so
i came to “return the favor”.I’m attempting to find things to improve my web site!I suppose its ok
to use some of your ideas!!
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.
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.
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?
I always used to read post in news papers but now as I am a
user of internet so from now I am using net for articles or reviews, thanks to web.
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!
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!