Codevs-1069拘束犯罪者

1069拘置犯罪者2010年NOIP全国リーグ向上組時間制限:1 s空間制限:128,000 KBテーマ説明Description S城には2つの刑務所があり、合計N人の犯罪者が拘置されており、番号はそれぞれ1~Nである.彼らの間の関係も自然に調和がとれていない.多くの犯罪者の間には長い間恨みが積もっていたが、客観的な条件が備わっていれば、いつでも衝突する可能性がある.我々は「恨み」で(正の整数値)ある2人の犯罪者の間の憎しみの程度を表し、恨みの値が大きいほど、この2人の犯罪者の間の恨みが多くなる.もし2人の恨みの値がcの犯罪者が同じ刑務所に収監されると、彼らの間に摩擦が発生し、影響力がcの衝突事件をもたらす.毎年年末には、警察署は本年中の刑務所のすべての衝突事件を影響力によって大きいから小さいまでリストを作って、S城Z市長のところに報告します.公務多忙なZ市長はリストの最初の事件の影響力だけを見に行き、影響が悪ければ警察局長の更迭を検討する.N人の犯罪者間の矛盾関係を詳しく考察した後、警察局長はプレッシャーを感じた.彼は犯罪者たちを2つの刑務所で再分配し、衝突事件の影響力が小さく、自分の烏紗帽を守るつもりだ.同じ刑務所にいる2人の犯罪者の間に憎しみがあれば、毎年のある時に摩擦が起こるに違いない.では、犯罪者をどのように分配すれば、Z市長が見た衝突事件の影響力を最小限に抑えることができるのだろうか.この最小値は少ないですか?Input Descriptionの第1の行為を記述する2つの正の整数NとMを入力し、それぞれ犯罪者の数と憎しみのある犯罪者の対数を表す.次のM行は3つの正の整数aj,bj,cjを行い、aj号とbj号の犯罪者の間に憎しみがあることを示し、その恨みの値はcjである.データは保証され、犯罪者のペアごとに1回しか現れません.出力はOutput Descriptionの全1行を記述し、Z市長が見たその衝突事件の影響力である.本年中に刑務所で衝突事件が発生しなかった場合は、0を出力します.サンプル入力Sample Input 4 6 1 4 2534 2 3 3 3512 1 2 28351 1 1 3 6618 2 4 1805 3 4 12884サンプル出力Sample Output 3512データ範囲および提示Data Size&Hint犯罪者間の不満値を以下の左図に示すように、右図に犯罪者の配分方法として示します.市長が見た衝突事件の影響力は3512(2番と3番の犯罪者によって引き起こされた)である.他のいかなる分法もこの分法より優れていない.【データ範囲】は30%のデータに対してN≦15である.70%のデータに対してN≦2000、M≦50000である.100%のデータに対してN≦20000、M≦100000である.
アイスティーのいくつかの方法は良いです(しかし、前にLOLIは私たちに2分233333を使わせました)

#include
#include
#include
#define N 100001
using namespace std;
int n,m,father[N],w[N]={0};
struct r {int x,y,v;}s[N];
int comp(r a,r b)
{if(a.v>b.v) return 1;return 0;}
int find(int x)
{
    if(x==father[x]) return x;
    int root=find(father[x]);
    if(w[father[x]]!=2)
     {
        if(w[x]==0)
         w[x]=w[father[x]];
        else
         w[x]=!w[father[x]];
     }
    father[x]=root;
    return root; 
}
int main()
{
    int i,s1;
    cin>>n>>m;
    for(i=1;i<=m;i++) cin>>s[i].x>>s[i].y>>s[i].v;
    for(i=1;i<=n;i++)
     {
        father[i]=i;
        w[i]=2;
     }
    sort(s+1,s+m+1,comp);
    for(i=1;i<=m;i++)
     {
        if(find(s[i].x)!=find(s[i].y))
         {
            s1=find(s[i].y);
            if(w[s[i].y]==2)
             w[s1]=1;
            else
             {
                if(w[s[i].y]==1)
                 w[s1]=0;
                else
                 w[s1]=1;
             }
            father[s1]=s[i].x;
            continue;
         }
        else 
         if(find(s[i].x)==find(s[i].y))
          if((w[s[i].x]==2&&w[s[i].y]==1)||(w[s[i].x]==1&&w[s[i].y]==2)||(w[s[i].x]==0&&w[s[i].y]==1)||(w[s[i].x]==1&&w[s[i].y]==0))
            continue;
          else
           {
            cout<return 0;
           }
     }
    cout<<0;
    return 0;
}