tyvj P1403 关押罪犯 题解

时间：2023-03-09 03:44:51
tyvj P1403 关押罪犯 题解
P1403 [NOIP2010]关押罪犯
时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

   S 城现有两座*，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时 可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯 被关押在同一*，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。
    每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
    在
详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱
帽。假设只要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的
影响力最小？这个最小值是多少？

输入格式

输入文件的每行中两个数之间用一个空格隔开。
第一行为两个正整数N 和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证1<=aj<bj<N,0<cj<=1,000,000,000 且每对罪犯组合只出现一次。

输出格式

输出共1 行，为Z 市长看到的那个冲突事件的影响力。如果本年内*中未发生任何冲突事件，请输出0。

测试样例1

输入

4 6

1 4 2534

2 3 3512

1 2 28351

1 3 6618

2 4 1805

3 4 12884

输出

3512

备注

【数据范围】
对于30%的数据有N≤ 15。
对于70%的数据有N≤ 2000，M≤ 50000。
对于100%的数据有N≤ 20000，M≤ 100000。
——————————————我是分割线————————————————————————
【解法一】
使用并查集，最快的方法。
一开始没注意数据范围，数组开小了，导致最后4个点RE，一个多钟头才查出来T_T
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstdlib>

 #include<iomanip>

 #include<cassert>

 #include<climits>

 #define maxn 100001

 #define F(i,j,k) for(int i=j;i<=k;i++)

 #define M(a,b) memset(a,b,sizeof(a))

 #define FF(i,j,k) for(int i=j;i>=k;i--)

 #define inf 0x7fffffff

 #define p 23333333333333333

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int f[maxn];

 struct sd

 {

     int a;

     int b;

     int c;

     int next;

 }edge[maxn];

 bool cmp(const sd& x,const sd& y)

 {

     return x.c>y.c;

 }

 int find(int x)

 {

     return f[x]==x?x:f[x]=find(f[x]);

 }

 int head[maxn];

 int cnt=;

 int addedge(int x,int y,int v)

 {

     cnt++;

     edge[cnt].a=x;

     edge[cnt].b=y;

     edge[cnt].c=v;

     edge[cnt].next=head[x];

     head[x]=cnt;

 }

 int main()

 {

     std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;

 //  freopen("data.in","r",stdin);

 //  freopen("data.out","w",stdout);

     int n,m;

     cin>>n>>m;

     F(i,,m){

         int x,y,z;

         cin>>x>>y>>z;

         addedge(x,y,z);

     }

     int x,y;

     for(int i=;i<=n*;i++)

         f[i]=i;

     sort(edge+,edge+m+,cmp);

     F(i,,m){

         x=find(edge[i].a);

         y=find(edge[i].b);

         if(x==y)

         {

             cout<<edge[i].c;

             return ;

         }

         f[y]=find(edge[i].a+n);

         f[x]=find(edge[i].b+n);

     }

     cout<<""<<endl;

     return ;

 }

tyvj 1403（1）

【解法二】

二分+二分图染色

前向星存储信息，用a数组单独储存怨气值，增加0（若无冲突，则输出0。

将a数组从小到大排序，二份答案。

若当前大于等于mid的关系能满足二分图的要求（用到二分图染色判定），则说明解小于等于mid,r=mid,否则说明解大于mid，就将L赋值为mid+1。

开了全局变量n、m后在主函数中又开了一次，导致错误，只输出0。又查了一个钟头........(大哭)

 /*

     Problem:tyvj 1403

     By:S.B.S.

 */

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstdlib>

 #include<iomanip>

 #include<cassert>

 #include<climits>

 #define maxn 200001

 #define F(i,j,k) for(int i=j;i<=k;i++)

 #define M(a,b) memset(a,b,sizeof(a))

 #define FF(i,j,k) for(int i=j;i>=k;i--)

 #define inf 0x7fffffff

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct EDGE

 {

     int y;

     int z;

     int next;

 }edge[maxn];

 int tot,it,n,m;

 int head[maxn],b[maxn],a[maxn];

 bool pd;

 inline void addedge(int x,int y,int z)

 {

     edge[++tot].y=y;

     edge[tot].z=z;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 int cmp(int a,int b)

 {

     return a<b;

 }

 inline void dfs(int x,int d)

 {

     if(pd==false) return;

     b[x]=d;

     for(int i=head[x];i!=;i=edge[i].next)

     {

         if(edge[i].z>it)

         {

 //            cout<<(int)pd<<endl;

             if(b[edge[i].y]==-) dfs(edge[i].y,-d);

             else

             {

                 if(b[edge[i].y]==d)

                 {

                     pd=false;

                     return;

                 }

             }

         }

     }

 }

 inline bool ok(int mm)

 {

     M(b,-);

     pd=true;

     it=a[mm];

 //    cout<<it<<endl; cout<<endl;

     F(i,,n)

     {

         if(b[i]==-) dfs(i,);

     }

     return pd;

 }

 int main()

 {

     std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;

 //  freopen("data.in","r",stdin);

 //  freopen("data.out","w",stdout);

 //    int n,m;

     cin>>n>>m;

     int x,y,z;

     tot=;

     M(head,);

     F(i,,m)

     {

         cin>>x>>y>>z;

         addedge(x,y,z);

         addedge(y,x,z);

         a[i+]=z;

     }

 //    for(int i=1;i<=tot;i++)cout<<edge[i].y<<' '<<edge[i].z<<' '<<edge[i].next<<endl;

     a[]=;

     sort(a+,a++m,cmp);

 //    for(int i=1;i<=m+1;i++)cout<<a[i]<<' ';

 //    cout<<endl;

     int left=,right=m+,mid;

     while(left<right)

     {

         mid=(left+right)/;

 //        cout<<left<<' '<<right<<' '<<mid<<endl;

         if(ok(mid)==true) right=mid;

         else left=mid+;

     }

     cout<<a[left]<<endl;

     return ;

 }

 /*

 4 6

 1 4 2534

 2 3 3512

 1 2 28351

 1 3 6618

 2 4 1805

 3 4 12884

 */

tyvj 1403（2）

相关文章