时间戳

首页 > 技术文章 > tyvj P1403 关押罪犯 题解

tyvj P1403 关押罪犯 题解

SBSOI 2016-07-04 09:05 原文

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
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cstdlib>
 8 #include<iomanip>
 9 #include<cassert>
10 #include<climits>
11 #define maxn 100001
12 #define F(i,j,k) for(int i=j;i<=k;i++)
13 #define M(a,b) memset(a,b,sizeof(a))
14 #define FF(i,j,k) for(int i=j;i>=k;i--)
15 #define inf 0x7fffffff
16 #define p 23333333333333333
17 using namespace std;
18 int read(){
19     int x=0,f=1;char ch=getchar();
20     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
21     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
22     return x*f;
23 }
24 int f[maxn];
25 struct sd
26 {
27     int a;
28     int b;
29     int c;
30     int next;
31 }edge[maxn];
32 bool cmp(const sd& x,const sd& y)
33 {
34     return x.c>y.c;
35 }
36 int find(int x) 
37 {
38     return f[x]==x?x:f[x]=find(f[x]);
39 }
40 int head[maxn];
41 int cnt=1;
42 int addedge(int x,int y,int v)
43 {
44     cnt++;
45     edge[cnt].a=x;
46     edge[cnt].b=y;
47     edge[cnt].c=v;
48     edge[cnt].next=head[x];
49     head[x]=cnt;
50 }
51 int main()
52 {
53     std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;
54 //  freopen("data.in","r",stdin);
55 //  freopen("data.out","w",stdout);
56     int n,m;
57     cin>>n>>m;
58     F(i,1,m){
59         int x,y,z;
60         cin>>x>>y>>z;
61         addedge(x,y,z);
62     }
63     int x,y;
64     for(int i=1;i<=n*2;i++)
65         f[i]=i;
66     sort(edge+1,edge+m+1,cmp);
67     F(i,1,m){
68         x=find(edge[i].a);
69         y=find(edge[i].b);
70         if(x==y) 
71         {
72             cout<<edge[i].c;
73             return 0;
74         }
75         f[y]=find(edge[i].a+n);
76         f[x]=find(edge[i].b+n);
77     }
78     cout<<"0"<<endl;
79     return 0;
80 }
tyvj 1403（1）

【解法二】

二分+二分图染色

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

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

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

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

  1 /*
  2     Problem:tyvj 1403
  3     By:S.B.S.
  4 */
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<cmath>
  9 #include<algorithm>
 10 #include<queue>
 11 #include<cstdlib>
 12 #include<iomanip>
 13 #include<cassert>
 14 #include<climits>
 15 #define maxn 200001
 16 #define F(i,j,k) for(int i=j;i<=k;i++)
 17 #define M(a,b) memset(a,b,sizeof(a))
 18 #define FF(i,j,k) for(int i=j;i>=k;i--)
 19 #define inf 0x7fffffff
 20 using namespace std;
 21 int read(){
 22     int x=0,f=1;char ch=getchar();
 23     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 24     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 25     return x*f;
 26 }
 27 struct EDGE
 28 {
 29     int y;
 30     int z;
 31     int next;
 32 }edge[maxn];
 33 int tot,it,n,m;
 34 int head[maxn],b[maxn],a[maxn];
 35 bool pd;
 36 inline void addedge(int x,int y,int z)
 37 {
 38     edge[++tot].y=y;
 39     edge[tot].z=z;
 40     edge[tot].next=head[x];
 41     head[x]=tot;
 42 }
 43 int cmp(int a,int b) 
 44 {
 45     return a<b;
 46 }
 47 inline void dfs(int x,int d)
 48 {
 49     if(pd==false) return;
 50     b[x]=d;
 51     for(int i=head[x];i!=0;i=edge[i].next)
 52     {
 53         if(edge[i].z>it)
 54         {
 55 //            cout<<(int)pd<<endl;
 56             if(b[edge[i].y]==-1) dfs(edge[i].y,1-d);
 57             else
 58             {
 59                 if(b[edge[i].y]==d)
 60                 {
 61                     pd=false;
 62                     return;
 63                 }
 64             }
 65         }
 66     }
 67 }
 68 inline bool ok(int mm)
 69 {
 70     M(b,-1);
 71     pd=true;
 72     it=a[mm];
 73 //    cout<<it<<endl; cout<<endl;
 74     F(i,1,n)
 75     {
 76         if(b[i]==-1) dfs(i,0);
 77     }
 78     return pd;
 79 }
 80 int main()
 81 {
 82     std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;
 83 //  freopen("data.in","r",stdin);
 84 //  freopen("data.out","w",stdout);
 85 //    int n,m;
 86     cin>>n>>m;
 87     int x,y,z;
 88     tot=0;
 89     M(head,0);
 90     F(i,1,m)
 91     {
 92         cin>>x>>y>>z;
 93         addedge(x,y,z);
 94         addedge(y,x,z);
 95         a[i+1]=z;
 96     }
 97 //    for(int i=1;i<=tot;i++)cout<<edge[i].y<<' '<<edge[i].z<<' '<<edge[i].next<<endl;
 98     a[1]=0;
 99     sort(a+1,a+1+m,cmp);
100 //    for(int i=1;i<=m+1;i++)cout<<a[i]<<' ';
101 //    cout<<endl;
102     int left=1,right=m+1,mid;
103     while(left<right)
104     {
105         mid=(left+right)/2;
106 //        cout<<left<<' '<<right<<' '<<mid<<endl;
107         if(ok(mid)==true) right=mid;
108         else left=mid+1;
109     }
110     cout<<a[left]<<endl;
111     return 0;
112 }
113 /*
114 4 6
115 1 4 2534
116 2 3 3512
117 1 2 28351
118 1 3 6618
119 2 4 1805
120 3 4 12884
121 */
tyvj 1403（2）

 

推荐阅读