算法基础OJ(22-E2-4)—危险品放置

发布于：2022-11-07 ⋅ 阅读:(10) ⋅ 点赞:(0) ⋅ 评论:(0)
危险品放置
现有若干危险品需要放置在A,B两个仓库。当两种特定的危险品放置在相同地点时即可能产生危险。我们用危险系数αi,j​表示危险品i,j放置在一起的危险程度。一些危险品即使放置在一起也不会产生任何危险，此时αi,j​=0，还有一些危险品即使单独放置也会产生危险，此时αi,i​>0。定义两个仓库整体的危险系数为max(maxi,j∈A​αi,j​,maxi,j∈B​αi,j​)，即放置在一起的所有危险品两两组合的危险系数的最大值。现在对于一组给定的危险系数，需要设计方案使得整体危险系数最小。
Input
输入共m+1行。 第一行两个整数n和m表示共有n种危险品，危险品之间的危险组合（危险系数非零的物品组合）共m种。接下来的m行，每行三个整数i,j,αij​表示(i,j)为危险组合（i,j可能相等），其危险系数为αi,j​>0。

数据规模 0<n≤100,000 0<m≤1,000,000

Output
输出共一行，包含一个整数，表示整体危险系数的最小值。
Sample Input 1 
3 3
1 2 4
2 3 3
1 3 2
Sample Output 1 
2
/*
将1,3放在A仓库，2放在B仓库
*/
并查集 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 1e6;

int n, m;
int e ;               
int res; 
bool NonFlag[N + 1];
int UpPoint[N + 1];

struct Couple
{
    int i;     
    int j;     
    int w; 
} dcoup[M + 1];

struct Point
{
    int set;       
    bool Flag; 
} Point[N + 1];

int Compare(const Couple &x, const Couple &y)
{
    return x.w < y.w;
}


bool noFlag(int s)
{
    if (s != UpPoint[s])
        NonFlag[s] ^= noFlag(UpPoint[s]);
    return NonFlag[s];
}

bool pola(int x)
{
    return (noFlag(Point[x].set) ^ Point[x].Flag);
}


int find(int s)
{
    if (s != UpPoint[s])
    {
        UpPoint[s] = find(UpPoint[s]);
        NonFlag[s] ^= NonFlag[UpPoint[s]];
    }
    return UpPoint[s];
}

int Set(int x)
{
    return find(Point[x].set);
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> dcoup[e].i >> dcoup[e].j >> dcoup[e].w;
        if (dcoup[e].i != dcoup[e].j) 
            e++;                              
        else if (dcoup[e].w > res)
            res = dcoup[e].w;
    }

    sort(dcoup, dcoup + e, Compare);
    for (int i = 0; i <= n; i++)
        UpPoint[i] = i;
    int sets = 0; 
    for (e = e-1; e >= 0; e--)
    {

        if (Point[dcoup[e].i].set == 0) 
        {
            if (Point[dcoup[e].j].set == 0) 
            {
                sets++;
                Point[dcoup[e].i].set = sets;
                Point[dcoup[e].i].Flag = dcoup[e].i < dcoup[e].j;
                Point[dcoup[e].j].set = sets;
                Point[dcoup[e].j].Flag = dcoup[e].i >= dcoup[e].j;
            }
            else
            {
                Point[dcoup[e].i].Flag = !pola(dcoup[e].j); 
                Point[dcoup[e].i].set = Set(dcoup[e].j);          
            }
        }
        else 
        {
            if (Point[dcoup[e].j].set == 0) 
            {
                Point[dcoup[e].j].Flag = !pola(dcoup[e].i);
                Point[dcoup[e].j].set = Set(dcoup[e].i);          
            }
            else
            {
                int i_flag = pola(dcoup[e].i);
                int j_flag = pola(dcoup[e].j);
                int is = Set(dcoup[e].i);
                int js = Set(dcoup[e].j);

                if (js == is) 
                {
                    if (i_flag == j_flag)
                        break;
                }
                else 
                {
                    if (i_flag == j_flag)
                    {
                        if (is < js) 
                        {
                            NonFlag[js] ^= 1; 
                            UpPoint[js] = is;      
                        }
                        else 
                        {
                            NonFlag[is] ^= 1; 
                            UpPoint[is] = js;    
                        }
                    }
                    else
                    {
                        if (is < js)       
                            UpPoint[js] = is; 
                        else
                            UpPoint[is] = js; 
                    }
                }
            }
        }
    }
	if(dcoup[e].w > res)
		cout <<dcoup[e].w;
	else
		cout<<res;

    return 0;
}
AC

在这里插入图片描述

网站公告

欢迎关注微信公众号

今日签到

点亮你在社区的每一天
签到

最新发布

热门文章