【HDU 5627】Clarke and MST



using namespace std;

const int N = 300000+9;

struct Edge{int u,v,val;}e[N];
int n,m,fa[N];

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 bool test(int x) {
	x = 1<<x-1; int tag = n-1;
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int i=1;i<=m;i++) if (e[i].val & x) 
		if (find(e[i].u) == find(e[i].v)) continue;
		else fa[find(e[i].u)] = find(e[i].v), tag--;
	if (!tag) { 
		int tmp=0;
		for (int i=1;i<=m;i++) if (e[i].val & x) e[++tmp] = e[i];
		m = tmp; return true;
	} else return false;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar();
	return ret;

int main(){
	int T; cin>>T; while (T--) {
		cin>>n>>m; int tag = n-1, vout = 0;
		for (int i=1;i<=n;i++) fa[i] = i;
		for (int i=1;i<=m;i++) {
			e[i].u = read(); e[i].v = read(); e[i].val = read();
			if (find(e[i].u) == find(e[i].v)) continue;
			else fa[find(e[i].u)] = fa[find(e[i].v)], tag--;
		if (tag) printf("0\n");
		else {
			for (int i=31;i;i--) if (test(i)) vout |= 1<<i-1;
	return 0;

24 thoughts to “【HDU 5627】Clarke and MST”

  1. Hmm it appears like your site ate my first comment (it was extremely long) so I
    guess I’ll just sum it up what I had written and say, I’m thoroughly enjoying your blog.
    I too am an aspiring blog blogger but I’m still new to the whole thing.
    Do you have any recommendations for rookie blog writers?

    I’d certainly appreciate it.

  2. whoah this weblog is fantastic i really like studying your posts.
    Stay up the good work! You know, a lot of persons are hunting round for this
    info, you could help them greatly.

  3. I don’t know whether it’s just me or if perhaps everybody else encountering issues with your website.
    It looks like some of the written text on your content are running off the screen. Can someone
    else please comment and let me know if this is happening to them as well?

    This could be a issue with my browser because I’ve had this happen previously.
    Appreciate it

  4. What’s up everyone, it’s my first go to see at this website, and paragraph is
    genuinely fruitful in favor of me, keep up posting these types of posts.

  5. I like the valuable information you provide in your articles.

    I’ll bookmark your weblog and check again here regularly.
    I’m quite certain I will learn plenty of new stuff right here!

    Good luck for the next!

  6. I am extremely impressed with your writing skills as well as with the layout on your weblog.

    Is this a paid theme or did you modify it yourself?
    Anyway keep up the excellent quality writing, it is rare to see a
    nice blog like this one today.

  7. Good day! I know this is kinda off topic but I’d figured I’d ask.
    Would you be interested in exchanging links or maybe guest authoring
    a blog post or vice-versa? My website goes over a lot of the same subjects as yours and I feel we could greatly
    benefit from each other. If you might be interested feel free to
    shoot me an email. I look forward to hearing from you!

    Wonderful blog by the way!

  8. Fantastic goods from you, man. I have remember your stuff previous to and you’re simply extremely wonderful.

    I actually like what you have got right here, certainly like what you are stating and the way through
    which you say it. You make it enjoyable and you continue to
    take care of to keep it wise. I cant wait to learn far
    more from you. That is really a wonderful website.

  9. F*ckin’ amazing things here. I’m very satisfied to look your article. Thank you a lot and i’m having a look ahead to touch you. Will you kindly drop me a mail?

  10. Hey! I’m at work surfing around your blog from my new iphone 4!
    Just wanted to say I love reading through your blog and look forward
    to all your posts! Keep up the superb work!

  11. Heya this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.

    I’m starting a blog soon but have no coding experience so I wanted
    to get guidance from someone with experience.
    Any help would be greatly appreciated!

  12. The other day, while I was at work, my sister stole my iphone and
    tested to see if it can survive a twenty five foot drop, just so she can be a
    youtube sensation. My apple ipad is now destroyed
    and she has 83 views. I know this is entirely off topic but I had to
    share it with someone!

  13. This design is wicked! You obviously know how to keep a reader entertained.
    Between your wit and your videos, I was almost moved
    to start my own blog (well, almost…HaHa!) Wonderful job.
    I really enjoyed what you had to say, and more than that, how
    you presented it. Too cool!

  14. I was very happy to search out this web-site.I wished to thanks to your time for this wonderful read!! I undoubtedly enjoying every little little bit of it and I’ve you bookmarked to check out new stuff you weblog post.


电子邮件地址不会被公开。 必填项已用*标注