毛豆

用户名：liuyt

访问量：16842

签　名：

等　　级
排　　名	1025
经　　验	3310
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

肺炎大作战-题解(C++代码)
浏览：186

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

二分+dfs染色法

　　作者: 毛豆　　　　发表时间：2019-10-07 10:52:25 浏览：193　|　评论：0　

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
说明

![](/image_editor_upload/20191007105117_96491.png)

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。

备注:

对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。
    
    //这个是用数组表示邻接表
    #include<bits/stdc++.h>
    #include<iostream>
    #include<cstdio>
    #include <cstring>
    using namespace std;
    const int E=100;//E为最大边数
    const int N=100;//n为最大定点数
    struct Edge
    {
        int u; //起点
        int v; //终点
        int next;//上一条边在edge数组中的位置
        int w; //权值
    } edge[E];//图
    int head[N];//记录输入的最后一个起始节点在edge数组中的位置
    int num;//数组下标；
    void init()
    {
        memset(head, 0, sizeof(head));//所有节点的初始为0，一开始节点没有与之相连的边
        num=1;//数组下表从1开始
    }
    void add_edge(int from,int to,int dis)
    {
        edge[num].u = from;//起点
        edge[num].v = to;//终点
        edge[num].w=dis;//权值
        edge[num].next=head[from];//记录以from节点出发的上一条边在edge数组的位置
        head[from]=num;  //更新以from节点出发的在edge数组的位置
        num++; //数组下标+1
    }
    int main()
    {
        int n,m,a,b,x;
        init();
        scanf("%d %d",&m, &n); //m为边数，n为定点数，默认从1开始
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d",&a,&b,&x);   //a是起点，b是终点
            add_edge(a,b,x);//存储信息
        }
        for(int u = 1; u <= n; u++)   //遍历所有的顶点，默认从1到n
        {
            for(int i = head[u]; i != 0; i = edge[i].next) //u顶点在edge数组中的位置（head(u)）；edge[i].next寻找上一条以i为起点的边在edge数组中的位置
            {
                //cout  << edge[i].next << endl;
                cout<<u<<" "<<"-->"<<edge[i].v<<" "<<edge[i].w<<endl;  //输出从顶点u到终点v
            }
        }
        return 0;
    }

//本代码可以ac
    #include<bits/stdc++.h>
    using namespace std;
    const int N=20010,M=200010;
    int n,m;
    int h[N],e[M],ne[M],w[M];
    int idx=1;//一定从第一条边开始
    int color[N];
    void add(int a,int b,int c)
    {
    	e[idx]=b;
    	w[idx]=c;
    	ne[idx]=h[a];
    	h[a]=idx++;
    }
    bool dfs(int u,int c,int limit)
    {
    	color[u]=c;
    	for(int i=h[u];i!=0;i=ne[i])
    	{
    		if(w[i]<=limit) continue;//
    		int j=e[i];
    		if(color[j])
    		{
    			if(color[j]==c) return false;
    		}
    		else if(!dfs(j,3-c,limit)) return false;
    	}
    	return true;
    }
    bool check(int weight)
    {
    	memset(color,0,sizeof(color));
    	for(int u=1;u<=n;u++)
    	{
    		if(color[u]==0)
    		{
    			if(!dfs(u,1,weight))
    			return false; 
    		}
    	}
    	return true;
    }
     
    int main()
    {
    	scanf("%d%d",&n,&m);
    	memset(h,0,sizeof(h));
    	while(m--) 
    	{
    		int a,b,c;
    		scanf("%d%d%d",&a,&b,&c);
    		add(a,b,c);
    		add(b,a,c);
    	}
    	int l=0,r=1e9;
    	while(l<r)
    	{
    		int mid=(l+r)/2;
    		if(check(mid)) r=mid;
    		else{
    			l=mid+1;
    		}
    	}
    	cout<<l;
     }

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C二级辅导-计负均正（C++代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

二分+dfs染色法

评论区

精彩推荐

高精度加法（C++代码）（大数加法）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1014题解

C语言训练-亲密数（C语言描述,反正怎么都能对）

勾股数（C语言代码）

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C二级辅导-计负均正 （C++代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

二分+dfs染色法

评论区

精彩推荐

高精度加法 （C++代码）（大数加法）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1014题解

C语言训练-亲密数 （C语言描述,反正怎么都能对）

勾股数 （C语言代码）

C二级辅导-计负均正（C++代码）

　　评论区

高精度加法（C++代码）（大数加法）

C语言训练-亲密数（C语言描述,反正怎么都能对）

勾股数（C语言代码）