题解

24 条题解

  • -1
    @ 2015-08-22 10:54:41

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    using namespace std;
    const int MAXN = 1000000;

    int f[MAXN*4];
    int bri = 0;

    struct NUM{
    int a, b, c;

    }num[MAXN];

    bool cmp(NUM u, NUM v){
    return u.c > v.c;

    }

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

    int main()
    {
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    scanf("%d%d%d", &num[i].a, &num[i].b, &num[i].c);
    sort(&num[1], &num[1]+m, cmp);
    for(int i=1; i<=n*2; i++)
    f[i] = i;
    for(int i=1; i<=m; i++){
    int bri1 = find(num[i].a) ,bri2 = find(num[i].b);
    if(bri1 == bri2){
    ans = num[i].c;
    break;
    }
    f[bri1] = find(num[i].b + n);
    f[bri2] = find(num[i].a + n);
    }
    printf("%d", ans);
    system("pause");

    return 0;

    }
    水一发(感谢楼下大神)

  • -1
    @ 2015-06-05 21:10:06

    二分答案+二分图染色
    有很多小细节最好调试时注意一下
    #include<cstdio>
    #include<iostream>
    #include<vector>
    #include<queue>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int MAX=0x7fffffff,N=100001;
    vector<int> to[N],cost[N];
    vector<int> link[N];
    queue<int> q;
    int col[N],a[100005];
    int n,m;
    int ANS;
    void ser(int,int);
    bool jud(int);
    int main()
    {
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
    int z,b,v;
    scanf("%d%d%d",&z,&b,&v);
    a[i]=v;
    to[z].push_back(b);to[b].push_back(z);
    cost[z].push_back(v);cost[b].push_back(v);
    }
    sort(a+1,a+m+1);
    if(jud(0)==true){
    cout<<0;
    return 0;
    }

    ser(1,m);

    return 0;
    }
    void ser(int l,int r){
    if(r==l){
    if(jud(a[l])==true){
    cout<<a[l];
    return ;
    }
    else{
    cout<<ANS;
    return ;
    }
    }

    int midd=(l+r)>>1;
    int mid=a[midd];
    if(jud(mid)==true){
    ANS=mid;
    r=midd;
    ser(l,r);
    }
    else{
    l=midd+1;
    ser(l,r);
    }
    }
    bool jud(int x){
    memset(link,0,sizeof(link));
    for(int i=1;i<=n;i++){
    for(int j=0;j<to[i].size();j++){
    int xx=to[i][j];int yy=cost[i][j];
    if(yy>x){
    link[i].push_back(xx);
    }
    }
    }

    memset(col,0,sizeof(col));

    for(int k=1;k<=n;k++){
    if(col[k]==0){
    while(q.size()>0) q.pop();
    q.push(k);
    while(q.size()>0){
    int gg=q.front();
    q.pop();
    if(col[gg]==0){
    col[gg]=1;
    }
    for(int h=0;h<link[gg].size();h++){
    int jj=link[gg][h];
    if(col[jj]==0){
    col[jj]=-col[gg];
    q.push(jj);
    }
    else{
    if(col[jj]==col[gg]){
    return false;
    }
    }

    }
    }

    }

    }
    return true;
    }

    • @ 2015-09-28 22:59:31

      嗯,我也是这样想的

  • -1
    @ 2014-09-08 00:32:39

    二分暴力

  • -2
    @ 2015-10-12 08:20:27

    program erfentu;
    var
    ans,maxn,i,l,j,k,n,m,tot,t:longint;
    aa:array[0..100000,0..2] of longint;
    o,color:array[0..100000] of longint;
    a,b,c:array[0..100000] of longint;
    vis:array[0..100000] of boolean;
    can:boolean;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(b) else exit(a);
    end;
    procedure addedge(p,q,w:longint);
    begin
    inc(tot);
    aa[tot,1]:=q;
    aa[tot,0]:=o[p];
    aa[tot,2]:=w;
    o[p]:=tot;
    end;
    procedure init;
    begin
    fillchar(color,sizeof(color),0);
    readln(n,m);
    tot:=0;
    for i:=1 to m do
    begin
    read(a[i],b[i],c[i]);
    addedge(a[i],b[i],c[i]);
    addedge(b[i],a[i],c[i]);
    end;
    ans:=maxlongint;
    fillchar(vis,sizeof(vis),false)
    end;
    procedure dfs(x:longint);
    begin
    vis[x]:=true;
    t:=aa[x,1];
    while (t<>0) do
    begin
    if vis[o[t]] then
    begin
    if (color[x]=color[o[x]]) then
    begin
    can:=false;
    ans:=max(ans,aa[x,2]);
    end;
    end
    else
    begin
    color[o[t]]:=1-color[x];
    dfs(o[t]);
    end;
    t:=aa[t,0];
    end;
    end;
    procedure work;
    begin
    for i:=1 to n do
    begin
    if not vis[i] then
    begin
    color[i]:=0;
    dfs(i);
    end;
    end;
    if can then writeln(0)
    else writeln(ans);
    end;
    begin
    init;
    work;
    end.

信息

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