第二届全国大学生算法设计与编程挑战赛-H-最大化-max

川长思鸟来 2022-12-21 10:59 157阅读 0赞

# Description #

有一张N个点的无向图，要求给每个点分配一个标号，使得任意一条边两端的点的标号差(绝对值)不能超过给出的常数D，要求在此基础上最大化标号的最大值减最小值。如果答案为+∞，则输出 -1。

# Input #

第一行两个数字n，D。  
接下来n行，每行n个数字，第i行j列的数字等于1，表示存在一条从i到j的无向边。也就输图的邻接矩阵。

# Output #

一行一个数字，表示答案。

# Sample Input 1 #

5 576  
0 1 1 0 0  
1 0 0 0 0  
1 0 0 0 0  
0 0 0 0 1  
0 0 0 1 0

# Sample Output 1 #

\-1

# 题解 #

如果图是一个连通图，那么结果就是从任一结点出发的最大深度乘以D；否则，结果为-1。因此，可以用广度优先搜索解决该问题。

# 代码 #

#include <iostream>
    #include <vector>
    using namespace std;
    struct Data { 
    	int i;
    	int level;
    };
    int main() { 
    	int n,d;
    	cin>>n>>d;
    	int G[n][n];
    	bool mark[n];
    	for(int i=0; i<n; i++) { 
    		mark[i]=false;
    		for(int j=0; j<n; j++)
    			cin>>G[i][j];
    	}
    	vector<Data> v;
    	Data dd;
    	dd.i=0;
    	dd.level=0;
    	v.push_back(dd);
    	mark[0]=true;
    	int pos=0;
    	while(pos<v.size()) { 
    		//v[pos]
    		for(int j=1; j<n; j++) { 
    			if(mark[j]==false && G[v[pos].i][j]==1) { 
    				Data dd;
    				dd.i=j;
    				dd.level=v[pos].level+1;
    				v.push_back(dd);
    				//v.push_back(j);
    				mark[j]=true;
    
    			}
    		}
    		pos++;
    	}
    	for(int j=0;j<n; j++) { 
    		if(mark[j]==false) { 
    			cout<<"-1";
    			return 0;
    		}
    	}
    	cout<<(v[v.size()-1].level)*d;
    	return 0;
    }