题解

24 条题解

  • 8
    @ 2016-07-09 17:24:56

    并查集做法

    #include <algorithm>
    #include <iostream>
    using namespace std;
    int n,m,f[40001],x,y;
    struct data{int a,b,c;} e[100001];
    bool gz(const data &a,const data &b) {return a.c > b.c;}
    int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
    int main() 
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
            cin>>e[i].a>>e[i].b>>e[i].c;
        for(int i=1;i<=n*2;i++)
            f[i]=i;//初始化 
        //有两个集 i友 与 i敌 用i+n表示
        sort(e+1,e+m+1,gz);//犯罪值降序 
        //因为要使最大冲突尽可能小,所以先分配大的(分离机会大) 
        for(int i=1;i<=m;i++) 
    {
            x=find(e[i].a);//找自己的宗族 
            y=find(e[i].b);
            if(x==y) 
            {
                cout<<e[i].c;
                return 0;
            }
            //因为只有个2监狱,那么对一个人只有友族与敌族 
            f[y] = find(e[i].a + n);//b朋友的宗族==a敌人的宗族; 
            f[x] = find(e[i].b + n);//敌人的敌人就是朋友 
        }
        cout<<0;//完全无冲突 
        return 0;
    }
    
  • 1
    @ 2020-10-28 19:53:25

    并查集
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,f[40001],x,y;
    struct data{
    int a,b,c;
    }e[100009];
    int gz(const data &a,const data &b){
    if(a.c>b.c)return 1;
    else return 0;
    }
    int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
    }
    int main(){
    freopen("prison.in","r",stdin);
    freopen("prison.out","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    cin>>e[i].a>>e[i].b>>e[i].c;
    for(int i=1; i<=n*2; i++)
    f[i]=i;
    sort(e+1,e+m+1,gz);
    for(int i=1; i<=m; i++){
    x=find(e[i].a);
    y=find(e[i].b);
    if(x==y){
    cout<<e[i].c;
    return 0;
    }
    f[y] = find(e[i].a + n);
    f[x] = find(e[i].b + n);
    }
    puts("0");
    return 0;
    }

  • 1
    @ 2017-10-22 17:12:33

    要使市长看到的事件影响最小,首先就可以想到贪心一下,把每两个人的冲突从大到小排个序。要尽量把冲突大的人分到不同监狱,但是怎么分不确定,我们就可以建立补集,采用两个并查集,把冲突大的两个人与彼此的补集相连。如果说当前有冲突的两个犯人已经被连在一起了,那么就停止。因为他们相连,就意味着他们有一位共同的敌人,通过这个敌人的补集他们连在了一起,而他们与这个敌人的冲突比他们之间的冲突要严重,所以他们两个在一个监狱最优。而我们是从大到小排序的,所以说先找到的就是这个监狱里冲突最大的。

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int f[40004];
    struct held{
        int a,b,y;
    }cri[100001];
    int cmp(held p,held q)
    {
        return p.y>q.y;
    }
    int fa(int x)                               //寻找祖先判断是否相连并沿途更新父节点。 
    {                                           //并查集基本操作。 
        if (f[x]!=x) f[x]=fa(f[x]);
        return f[x];
    }
    int main()
    {
        int n,m,i,g,h;
        bool ff=1;
        scanf("%d%d",&n,&m);
        for (i=1;i<=m;i++) scanf("%d%d%d",&cri[i].a,&cri[i].b,&cri[i].y);
        for (i=1;i<=2*n;i++) f[i]=i;                       //初始化,自己是自己的父亲。 
        sort(cri+1,cri+1+m,cmp);
        for (i=1;i<=m;i++)
        {
            g=fa(cri[i].a); h=fa(cri[i].b);
            if (g==h) {printf("%d",cri[i].y); ff=0; break;}    //是否已经相连。 
            f[h]=fa(cri[i].a+n);                               //与彼此的补集相连。 
            f[g]=fa(cri[i].b+n);
        }
        if (ff) putchar('0');                                   //没有一点矛盾。 
        return 0;
    }
    
  • 0
    @ 2017-05-09 22:25:06

    类似最小生成树找到最大生成树,然后dfs进行染色,也就是把这棵树上相邻的点放进不同的监狱,之后考虑不在树上的边,如果边的两端点的颜色不同,不用考虑,如果相同,更新答案
    //#include "stdafx.h"
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #define maxn (int)1e7+10
    #define INF 99999999
    #define LDB long double
    #define LL long long
    using namespace std;
    int v[400000], ne[400000], num[400000], len[400000], col[400000],head[400000],pre[400000],s[400000],t[400000],flag[400000];
    int cot;
    int addedge(int s, int t){
    v[cot] = t; ne[cot] = head[s]; head[s] = cot++;
    return 0;
    }
    int cmp(int a, int b) {
    return len[a] > len[b];
    }
    int dfs(int s) {
    for (int i = head[s]; i != -1; i = ne[i]) {
    if (col[v[i]] != -1)
    continue;
    col[v[i]] = 1 - col[s];
    dfs(v[i]);
    }
    return 1;
    }
    int findf(int x) {
    int p = x;
    while (pre[x] != x)
    x = pre[x];
    int c;
    while (p != x) {
    c = pre[p];
    pre[p] = x;
    p = c;
    }
    return x;
    }
    int add(int a, int b) {
    int f1 = findf(a); int f2 = findf(b);
    if (f1 != f2) {
    pre[f2] = f1;
    }
    return 0;
    }
    int main() {
    int n, m;
    while (scanf("%d%d", &n, &m)!= EOF) {
    cot = 0;
    memset(head, -1, sizeof(head));
    memset(flag, 0, sizeof(flag));
    memset(col, -1, sizeof(col));
    for (int i = 0; i <= n; i++)
    pre[i] = i;
    for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &s[i], &t[i], &len[i]);
    num[i] = i;
    }
    sort(num, num + m, cmp);
    for (int i = 0; i < m; i++) {
    int j = num[i];
    if (findf(s[j]) != findf(t[j])) {
    addedge(s[j], t[j]);
    addedge(t[j], s[j]);
    flag[num[i]] = 1;
    add(s[j], t[j]);
    }
    }
    dfs(1);
    int ans = 0;
    for (int i = 0; i < m; i++) {
    if (flag[i])
    continue;
    if (col[s[i]] == col[t[i]])
    ans = max(ans, len[i]);
    }
    printf("%d\n", ans);
    }
    }

  • 0
    @ 2015-10-08 09:24:48

    之前用二分图染色那种方法做着试了试 得了90 一个点超时 应该是我写的那个太丑了 有人用二分图过了
    下面用的是并查集 但我理解了半天才明白

    并查集用来维护元素在同一个集合比较好用 比较好理解 即他们的根相等 他们就在同一个集合
    现在要维护的是不在同一个集合 不好弄
    如果我们用f[i]=j表示i与j不在同一个监狱
    那么就会出现这种错误
    比如a与b不在一个监狱 b与c不在一个监狱
    那a与c呢 若按照上述方法 那么此时a与c的祖先一定相等 也就是代表a与c不在一个监狱 而事实上a与c是在同一个监狱里的

    所以我们设了一些虚的点
    比如现在我们要合并i j
    那么
    f[find(i)]=find(j+n)
    f[find(j)]=find(i+n)
    表示i与j不在同一个监狱
    这样i与j的祖先是不同的 避免了上述错误

    分析这个例子
    4 6
    1 2 9
    3 4 7
    1 3 6
    2 3 3
    1 4 2
    2 4 1
    按边权排好序后开始合并
    1 2 9
    f[1]=2+n
    f[4]=3+n
    3 4 7
    f[3]=4+n
    f[4]=3+n
    1 3 6
    f[find(1)]=find(3+n)---->f[2+n]=3+n
    f[find(3)]=find(1+n)---->f[4+n]=1+n
    2 3 3
    f[find(2)]=find(3+n)---->f[1+n]=3+n
    f[find(3)]=find(2+n)---->f[1+n]=3+n
    此时f[find(2)]=f[find(3)]就出现了矛盾
    两个人分别和他们的祖先不在同一个监狱里 而他们的祖先是一个人 就注定他们两个人必须在同一个监狱
    此时的就得出了答案

    还有人的做法是另开了一个数组 本质上都是相同的

    var
    a,b,c:array[0..100009] of longint;
    f:array[0..40009] of longint;
    x,y,ans,i,n,m:longint;
    procedure qsort(l,r:longint);
    var i,j,bi,ti:longint;
    begin
    i:=l; j:=r;
    bi:=c[(l+r) div 2];
    repeat
    while c[i]>bi do inc(i);
    while c[j]<bi do dec(j);
    if i<=j then
    begin
    ti:=a[i]; a[i]:=a[j]; a[j]:=ti;
    ti:=b[i]; b[i]:=b[j]; b[j]:=ti;
    ti:=c[i]; c[i]:=c[j]; c[j]:=ti;
    inc(i); dec(j);
    end;
    until i>j;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
    end;
    function find(x:longint):longint;
    begin
    if f[x]=x then exit(x);
    f[x]:=find(f[x]);
    exit(f[x]);
    end;
    begin
    readln(n,m);
    for i:=1 to m do read(a[i],b[i],c[i]);
    qsort(1,m);
    //writeln; for i:=1 to m do writeln(a[i],' ',b[i],' ',c[i]);
    for i:=1 to 2*n do f[i]:=i;
    for i:=1 to m do
    begin
    x:=find(a[i]);
    y:=find(b[i]);
    if x=y then
    begin
    ans:=c[i];
    break;
    end else
    begin
    f[x]:=find(b[i]+n);
    f[y]:=find(a[i]+n);
    end;
    end;
    writeln(ans);
    end.

    • @ 2016-11-13 13:41:31

      讲解的**1 2 9**这个数据出错;

      应该是*f[2]=1+n*
      而非*f[4]=3+n*

  • 0
    @ 2015-05-11 20:25:18

    type
    node=record
    head,tail,data:longint;
    end;
    var
    n,m,i,fx,fy:longint;
    link:array[1..100000]of node;
    father,enemy:array[1..20000]of longint;
    procedure qsort(l,r:longint);
    var
    i,j,mid:longint;
    t:node;
    begin
    i:=l;
    j:=r;
    mid:=link[(l+r) div 2].data;
    repeat
    while link[i].data>mid do inc(i);
    while link[j].data<mid do dec(j);
    if i<=j then
    begin
    t:=link[i];link[i]:=link[j];link[j]:=t;
    inc(i);dec(j);
    end;
    until i>j;
    if i<r then qsort(i,r);
    if l<j then qsort(l,j);
    end;
    function getfather(u:longint):longint;
    begin
    if father[u]=u then exit(u)
    else father[u]:=getfather(father[u]);
    exit(father[u]);
    end;
    procedure union(u,v:longint);
    var
    fx,fy:longint;
    begin
    fx:=getfather(u);
    fy:=getfather(v);
    father[fx]:=fy;
    end;
    procedure init;
    var
    i:longint;
    begin
    readln(n,m);
    for i:=1 to m do read(link[i].head,link[i].tail,link[i].data);
    qsort(1,m);
    for i:=1 to n do father[i]:=i;
    fillchar(enemy,sizeof(enemy),0);
    end;
    procedure work;
    var
    i,j,fx,fy:longint;
    begin
    for i:=1 to m do
    begin
    fx:=getfather(father[link[i].head]);
    fy:=getfather(father[link[i].tail]);
    if fx=fy then
    begin
    write(link[i].data);
    halt;
    end;
    if enemy[link[i].head]=0 then enemy[link[i].head]:=link[i].tail;
    if enemy[link[i].tail]=0 then enemy[link[i].tail]:=link[i].head;
    union(enemy[link[i].head],link[i].tail);
    union(enemy[link[i].tail],link[i].head);
    end;
    end;
    begin
    init;
    work;
    write('0');
    end.

  • 0
    @ 2014-10-15 17:40:29

    #include<iostream>
    #include<fstream>
    #include<algorithm>

    using namespace std;

    struct Enemynode
    {
    int first,second,cost;
    bool operator < (const Enemynode b)const
    {
    return cost>b.cost;
    }
    }Enemy[100001];

    int N,M,father[40001];

    int get_father(int x)
    {
    if (x==father[x]) return x;
    return father[x]=get_father(father[x]);
    }

    int main()
    {
    cin>>N>>M;
    for(int i=1;i<=(N<<1);i++)
    father[i]=i;
    for(int i=0;i<M;i++)
    cin>>Enemy[i].first>>Enemy[i].second>>Enemy[i].cost;
    sort(Enemy,Enemy+M);
    for(int i=0;i<M;i++)
    {
    int x=get_father(Enemy[i].first),y=get_father(Enemy[i].second);
    if (x==y)
    {
    cout<<Enemy[i].cost;
    return 0;
    }
    father[x]=get_father(Enemy[i].second+N);
    father[y]=get_father(Enemy[i].first+N);
    }
    cout<<0;
    return 0;
    }

  • 0
    @ 2014-08-07 19:46:54

    var n,m,i,j,x,y:longint;a,b,c,f:array[0..100000] of longint;
    procedure xc(var x,y:longint);
    var t:longint;
    begin
    t:=x;x:=y;y:=t;
    end;
    procedure qsort(l,r:longint);
    var x,y,mid:longint;
    begin
    x:=l; y:=r; mid:=c[(x+y) div 2];
    repeat
    while c[x]>mid do inc(x);
    while c[y]<mid do dec(y);
    if x<=y then
    begin
    xc(a[x],a[y]);
    xc(b[x],b[y]);
    xc(c[x],c[y]);
    inc(x); dec(y);
    end;
    until x>y;
    if x<r then qsort(x,r);
    if l<y then qsort(l,y);
    end;

    procedure shut(i:integer);
    begin
    writeln(c[i]);
    halt;
    end;

    function getf(x:longint):longint;
    begin
    if f[x]=x then exit(x);
    exit(getf(f[x]));
    end;
    begin
    readln(n,m);
    for i:=1 to m do
    readln(a[i],b[i],c[i]);
    qsort(1,m);
    for i:=1 to n do f[i]:=i;
    for i:=1 to m do
    begin
    x:=getf(a[i]);
    y:=getf(b[i]);
    if x=y then shut(i);
    f[x]:=y;
    end;
    writeln(0);
    end.

  • 0
    @ 2014-08-02 12:49:47

    贪心+并查集

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int f[20004],g[20004];
    int n,m;
    struct Edge
    {
    int c,u,v;
    inline void Read()
    {
    scanf("%d%d%d",&u,&v,&c);
    }
    }C[100005];
    int getf(int x)
    {
    if (x==f[x]) return x;
    int fa=getf(f[x]);
    g[x]^=g[f[x]];
    return f[x]=fa;
    }
    inline bool cmp(const Edge& A,const Edge& B)
    {
    return A.c>B.c;
    }
    int main()
    {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    C[i].Read();
    for (int i=1;i<=n;i++)
    f[i]=i;
    sort(C+1,C+m+1,cmp);
    for (int i=1;i<=m;i++)
    {
    int u=getf(C[i].u),v=getf(C[i].v);
    if (u==v)
    {
    if (g[C[i].u]==g[C[i].v])
    {
    printf("%d\n",C[i].c);
    return 0;
    }
    continue;
    }
    g[v]=g[C[i].u]^g[C[i].v]^1;
    f[f[v]]=u;
    }
    puts("0");
    return 0;
    }

  • 0
    @ 2014-02-04 15:21:15

    测试数据 #0: Accepted, time = 0 ms, mem = 1768 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1768 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1772 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1776 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 1776 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 1772 KiB, score = 10
    测试数据 #6: Accepted, time = 31 ms, mem = 1772 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 1776 KiB, score = 10
    测试数据 #8: Accepted, time = 62 ms, mem = 1772 KiB, score = 10
    测试数据 #9: Accepted, time = 62 ms, mem = 1768 KiB, score = 10
    Accepted, time = 216 ms, mem = 1776 KiB, score = 100

    我的思路是基于一个基本结论的(在这道题)
    由于只有两个监狱,所以
    若a和b不在同一监狱
    若b和c不在同一监狱
    则a和c在同一监狱。
    而我的原则是,尽量把两个怨气值大的两个人关到不同的监狱中去
    所以首先就快排(按怨气值从大到小)
    然后就开始处理怨气了(当然是从最大的开始)——
    1. 如果这个两个人已经在同一监狱中了,ok,不用干了,他们的怨气值就是最大(什么,你要把他们分开,那会导致更大的怨气)
    a. 把这两个人关到不同的监狱(怎么关?)
    b. a和b的监狱不同,把a的祖先改为(b+n)的祖先。同理b的祖先改为……
    c. 为什么这样干?因为倘若再有一个人c和b合不来,然后c的祖先同样的也要置为b+n的祖先。如此以来a和c的父亲也就相同。而父亲相同就代表他们在同一监狱。于是……

    比较混乱,看看代码吧

    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>

    typedef struct {
    int a,b,cost;
    }node;

    node person[100002];
    int f[40002];
    int n,m;

    void init()
    {
    int i;
    scanf("%d%d",&n,&m);
    for (i = 1;i <= m;i++)
    scanf("%d%d%d",&person[i].a,&person[i].b,&person[i].cost);
    }

    int tmp;
    void swap(node *a,node *b)
    {
    tmp = a->a; a->a = b->a; b->a = tmp;
    tmp = a->b; a->b = b->b; b->b = tmp;
    tmp = a->cost; a->cost = b->cost; b->cost = tmp;
    }

    node mid;
    void quicksort(node *front,node *rear)
    {
    node *i,*j;
    i = rand()%(rear-front+1)+front;
    mid.a = i->a; mid.b = i->b; mid.cost = i->cost;
    swap(rear,i);
    i = front; j = rear;
    while (i <= j){
    while (i->cost > mid.cost) i++;
    while (j->cost < mid.cost) j--;
    if (i <= j) {
    swap(i,j);
    i++,j--;
    }
    }
    if (i < rear) quicksort(i,rear);
    if (j > front) quicksort(front,j);
    }

    long find(int a)
    {
    if (a == f[a])
    return a;
    else
    return f[a] = find(f[a]);
    }

    int main()
    {
    int i,sa,sb,ans;
    /*freopen("zui.in","r",stdin);
    freopen("zui.out","w",stdout);*/
    for (i = 0;i < 100002;i++)
    person[i].cost = 0;
    init();
    srand(time(NULL));
    quicksort(&person[1],&person[m]); /*按怨气值排序从大到小*/
    for (i = 1;i <= 2*n;i++)
    f[i] = i; /*每个人的“父”为自己*/
    ans = -1;
    for (i = 1;i <= m;i++) {
    sa = find(person[i].a); /*甲方父*/
    sb = find(person[i].b); /*乙方父*/
    if (sa == sb) {/*父相同
    即两人已经在同一个监狱中),题目所求的就是两个人的怨气值*/
    ans = i;
    break;
    } else {
    f[sa] = f[find(person[i].b+n)];
    f[sb] = f[find(person[i].a+n)];/*甲乙关到不同的监狱中*/
    }
    }
    if (ans == -1)
    printf("0");
    else
    printf("%d",person[ans].cost);
    /*fclose(stdin);
    fclose(stdout);*/
    return 0;
    }

    • @ 2015-07-04 19:14:28

      这代码是刚从pascal转C的时候写的吧。。

  • 0
    @ 2013-11-07 13:19:03

    二分答案,将边权大于二分值的边加入图中,然后判断是否为二分图。
    测试数据 #0: Accepted, time = 0 ms, mem = 4652 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 4652 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 4656 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 4656 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 4656 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 4656 KiB, score = 10
    测试数据 #6: Accepted, time = 62 ms, mem = 4656 KiB, score = 10
    测试数据 #7: Accepted, time = 62 ms, mem = 4656 KiB, score = 10
    测试数据 #8: Accepted, time = 140 ms, mem = 4656 KiB, score = 10
    测试数据 #9: Accepted, time = 171 ms, mem = 4652 KiB, score = 10
    Accepted, time = 480 ms, mem = 4656 KiB, score = 100

  • 0
    @ 2013-09-26 20:18:17

    乱七八糟的方法,以为可以暴力的,结果wa#include<stdio.h>
    int main()
    {
    int n,m; //罪犯人数,有矛盾的对数.
    int i,j;
    long a[20000];long b[20000];long c[20000]; //罪犯编号,怨气值.
    long d[20000];long e[20000];long f[20000]; //进入甲乙监狱的人,相应怒气值.
    int answer;
    scanf("%l",&n);
    scanf("%l",&m);
    for ( j=0 ; j<m ; j++)
    {
    scanf("%l",&a[j]);
    scanf("%l",&b[j]);
    scanf("%l",&c[j]);
    }
    for (i=0 ; i<j ; i++)
    {
    if ( c[j] > c[j+1] )
    {
    d[i]=c[j];
    e[i]=a[j];
    f[i]=b[j];
    }
    for ( i=0 ; i<j ; i++)
    {
    if (f[i]>f[i+1])
    answer=f[i+1];
    }
    }
    printf("%l",answer);
    return 0;
    }

  • 0
    @ 2013-09-26 19:49:06

    #include<stdio.h>
    typedef struct
    {
    int a,b,anger;

    }Node;

    int n,m,ans;
    int f[40002];
    Node crime[100001];

    void qsort(int l,int r)
    {
    int i=l,j=r,mid=crime[(i+j)/2].anger;
    while(i<=j)
    {
    while(crime[i].anger>mid) i++;

    while(crime[j].anger<mid) j--;
    if(i<=j)
    {
    Node t=crime[i];
    crime[i]=crime[j];
    crime[j]=t;
    i++;
    j--;
    }
    }
    if(i<r) qsort(i,r);
    if(j>l) qsort(l,j);

    }

    int find(int x)
    {
    if(x!=f[x])
    f[x]=find(f[x]);
    return f[x];
    }

    int main()
    { int n,m,i,j,sa,sb;
    scanf("%d%d",&n,&m);
    for(i=1;i<m;i++)
    scanf("%d%d%d",&crime[i].a,&crime[i].b,&crime[i].anger);

    qsort(1,m);
    for(i=1;i<=2*n;i++)
    f[i]=i;
    for(i=1;i<m+1;i++)
    {
    sa=find(crime[i].a);

    sb=find(crime[i].b);

    if(sa==sb)
    {
    ans=i;

    break;

    }
    else
    {
    f[sa]=f[find(crime[i].b+n)];
    f[sb]=f[find(crime[i].a+n)];
    }

    }
    printf("%d",crime[ans].anger);

    return 0;

    }

    测试数据 #0: Accepted, time = 0 ms, mem = 1872 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1868 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1868 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1872 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1864 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 1864 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 1868 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 1864 KiB, score = 10
    测试数据 #8: Accepted, time = 62 ms, mem = 1864 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 1868 KiB, score = 10
    Accepted, time = 232 ms, mem = 1872 KiB, score = 100

  • -1
    @ 2017-09-20 21:15:52

    91ms,似乎是目前为止最快的代码
    如果想要更快可以加点代码,可以50ms左右

    思路来自此博客

    关键思路:
    既然本题是两个集合(显然使用并查集),那么如果a和b不在一个集合,b和c不在一个集合,a必须和c在一个集合
    那么本题就是尽可能让大边的两个罪犯不要满足上述情况(先把所有边从大到小排一遍),一旦出现上述情况必须在一个集合内,那么即为解(因为排序过,所以必定比剩下的边都大)

    所以

    这个大佬的思路是用f[i] 记录与 i 同监狱的人,f[i+n]记录与 i 不同监狱的人。(即对立集合元素)

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn =20000;
    const int maxm =100000;
    
    using namespace std;  
    
    int n,m,f[maxn*2+20];  
    
    inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
    
    struct tnode{int a,b,c;}q[maxm+20]; 
    
    bool cmp(tnode x,tnode y)  {return x.c>y.c;}  
    
    int find(int x)  {return f[x]=(f[x]==x)?x:find(f[x]);}  
    int main()  
    {  
      int i,j,k,r1,r2,r3,r4;  
      n=read();m=read();
      for(i=1;i<=n;i++)f[i]=i,f[i+n]=i+n;  
      for(i=1;i<=m;i++) q[i].a=read(),q[i].b=read(),q[i].c=read();  
      sort(q+1,q+m+1,cmp);  
      for(i=1;i<=m;i++)  
        {  
          r1=find(q[i].a),r2=find(q[i].a+n);  
          r3=find(q[i].b),r4=find(q[i].b+n);  
          if(r1==r3 || r2==r4)break;  
          f[r3]=r2,f[r4]=r1;  
        }  
      if(i>m)printf("0\n");  
      else printf("%d\n",q[i].c);    
      return 0;  
    }  
    
    
  • -1
    @ 2017-01-30 15:52:20

    并查集+拆点
    #include <algorithm>
    #include <bitset>
    #include <cctype>
    #include <complex>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <set>
    #include <stack>
    #include <utility>
    #include <vector>

    using namespace std;

    #define rep(i,a,b) for(int i=(a);i<(b);i++)
    #define irep(i,a,b) for(int i=(a);i>(b);i--)
    #define reset(a,c) memset(a,c,sizeof(a))

    typedef long long int64;

    const int inf = 0x3f3f3f3f;

    const int maxN = 20000 + 5;
    const int maxM = 100000 + 5;

    struct Edge
    {
    int v1, v2, w;
    bool operator < (const Edge& x) const
    {
    return w > x.w;
    }
    void read()
    {
    scanf ("%d%d%d", &v1, &v2, &w);
    }
    };

    Edge edge[maxM];
    int ufs[maxN << 1];
    int N, M;

    void input()
    {
    scanf ("%d%d", &N, &M);
    rep (i, 0, M) edge[i].read();
    }

    int find (int x)
    {
    return ufs[x] == x ? x : ufs[x] = find (ufs[x]);
    }

    void link (int x, int y)
    {
    ufs[find (x)] = find (y);
    }

    int solve()
    {
    rep (i, 1, (N << 1) | 1) ufs[i] = i;
    sort (edge, edge + M);
    rep (i, 0, M)
    {
    int f1 = find (edge[i].v1);
    int f2 = find (edge[i].v2);
    if (f1 == f2) return edge[i].w;
    link (edge[i].v1, edge[i].v2 + N);
    link (edge[i].v2, edge[i].v1 + N);
    }
    return 0;
    }

    int main()
    {
    input();
    printf ("%d\n", solve() );
    return 0;
    }

  • -1
    @ 2016-08-08 19:34:20

    简单的二分加二分图染色
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;

    const int INF = 1000000000;
    const int maxn = 20000 + 5;
    const int maxm = 100000 + 5;
    int n, m;
    int L, R;
    int color[maxn];
    vector<int> G[maxn];

    struct Edge {
    int from, to, dist;
    Edge (int a, int b, int c) : from(a), to(b), dist(c) {}
    };

    vector<Edge> edges;

    void AddEdge (int u, int v, int w) {
    G[u].push_back(edges.size());
    edges.push_back(Edge(u, v, w));
    G[v].push_back(edges.size());
    edges.push_back(Edge(v, u, w));
    }

    int k;
    bool bipartite (int u) {
    for (int i = 0; i < G[u].size(); i++) {
    Edge& e = edges[G[u][i]];
    if (e.dist <= k) continue;
    if (color[e.to] == color[u]) return false;
    if (!color[e.to]) {
    color[e.to] = 3 - color[u];
    if (!bipartite(e.to)) return false;
    }
    }
    return true;
    }

    bool check (int test) {
    k = test;
    for (int i = 0; i < n; i++) color[i] = 0;
    for (int i = 0; i < n; i++)
    if (!color[i]) {
    color[i] = 1;
    if (!bipartite(i)) return false;
    }
    return true;
    }

    int main ()
    {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w); u--; v--;
    R = max(R, w);
    AddEdge(u, v, w);
    }

    while (L < R) {
    int M = L + (R - L) / 2;
    if (check(M)) R = M; else L = M + 1;
    }
    cout << L;
    return 0;
    }
    ```

  • -1
    @ 2015-11-05 21:07:45

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<cstdlib>
    using namespace std;
    struct thief{
    int one,two,anger;
    };
    struct thief a[100001];
    int n,m,father[40005];
    int comp(const struct thief&x,const struct thief&y)
    {
    return x.anger>y.anger;
    }
    void init()
    {
    int i;
    scanf("%d%d",&n,&m);;
    for(i=1;i<=m;i++){
    scanf("%d%d%d",&a[i].one,&a[i].two,&a[i].anger);
    }
    for(i=1;i<=2*n;i++){
    father[i]=i;
    }
    sort(a+1,a+m+1,comp);
    }
    int find(int t)
    {
    if(father[t]!=t){
    father[t]=find(father[t]);
    return father[t];
    }
    else{
    return t;
    }
    }
    void work()
    {
    int i;
    for(i=1;i<=m;i++){
    int temp1=find(a[i].one);
    int temp2=find(a[i].two);
    if(temp1!=temp2){
    int temp3=find(a[i].one+n);
    if(temp3!=temp2){
    father[temp3]=temp2;
    }
    int temp4=find(a[i].two+n);
    if(temp1!=temp4){
    father[temp1]=temp4;
    }
    }
    else{
    printf("%d",a[i].anger);
    return;
    }
    }
    printf("0");
    }
    int main()
    {
    init();
    work();
    return 0;
    }

  • -1
    @ 2015-10-24 15:39:51

    二分图染色和二分答案即可
    第一次写二分图染色,诸多细节都没有考虑到
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>

    using namespace std;

    struct P {
    int x, y, len;
    } p[100005];
    struct Node {
    int nextNode;
    Node *next;
    } *node[20005], pool[300005];

    int n, m, cnt;
    bool flag[100005];
    bool f[20005];
    int color[20005];
    bool f2[20005];

    bool dfs(int u) {
    f2[u] = true;
    for (Node *c = node[u]; c; c = c->next) {
    int v = c->nextNode;
    if (color[u] == color[v]) {
    return false;
    }
    if (!color[v]) {
    color[v] = 3 - color[u];
    if (!dfs(v))
    return false;
    }
    }
    return true;
    }
    bool check(int mid) {
    if (mid == m)
    return true;
    memset(color, 0, sizeof (color));
    memset(node, 0, sizeof (node));
    memset(pool, 0, sizeof (pool));
    memset(f2, 0, sizeof (f2));
    memset(f, 0, sizeof (f));
    cnt = 0;
    for (int i = mid + 1; i <= m; ++i) {
    Node *c = &pool[++cnt];
    c->nextNode = p[i].y;
    c->next = node[p[i].x];
    node[p[i].x] = c;
    c = &pool[++cnt];
    c->nextNode = p[i].x;
    c->next = node[p[i].y];
    node[p[i].y] = c;
    f[p[i].x] = f[p[i].y] = true;
    }
    for (int i = 1; i <= n; ++i) {
    if (!f[i])
    continue;
    if (!f2[i]) {
    color[i] = 1;
    if (!dfs(i)) {
    return false;
    }
    }
    }
    return true;
    }
    bool cmp(P a, P b) {
    return (a.len < b.len);
    }
    int main(int argc, const char *argv[]) {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)
    scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].len);
    sort(p + 1, p + m + 1, cmp);
    int ans = 0;
    if (check(0)) {
    printf("0\n");
    return 0;
    }
    int l = 1, r = m;
    while (l <= r) {
    int mid = (l + r) / 2;
    if (flag[mid])
    break;
    flag[mid] = true;
    if (check(mid)) {
    ans = mid;
    r = mid;
    }
    else {
    l = mid + 1;
    }
    }
    printf("%d\n", p[ans].len);
    return 0;
    }

  • -1
    @ 2015-08-24 08:46:33

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>

    using namespace std;

    int n , m;

    struct edge
    {
    int x , y;
    int v;
    };

    edge e[100000 + 2];

    int cmp( edge a , edge b )
    {
    if( a.v > b.v )
    return 1;
    return 0;
    }

    int i;
    int pre[400000 + 10];

    int find( int x )
    {
    if( x == pre[x] )
    return x;
    return pre[x] = find( pre[x] );
    }

    void merge( int a , int b )
    {
    pre[ find( a ) ] = find( b );
    return;
    }

    int main()
    {
    scanf( "%d %d" , &n , &m );
    for( i = 1 ; i <= m ; i++ )
    scanf( "%d %d %d" , &e[i].x , &e[i].y , &e[i].v );
    for( i = 1 ; i <= n * 2 ; i++ )
    pre[i] = i;
    sort( e + 1 , e + m + 1 , cmp );
    for( i = 1 ; i <= m ; i++ )
    {
    if( find( e[i].x ) != find( e[i].y ) )
    {
    merge( e[i].x , e[i].y + n );
    merge( e[i].x + n , e[i].y );
    }
    else
    {
    cout << e[i].v << endl;
    return 0;
    }
    }
    cout << 0 << endl;
    return 0;
    }

信息

ID
1776
难度
6
分类
图结构 | 二分图 点击显示
标签
递交数
3545
已通过
1017
通过率
29%
被复制
12
上传者