바 쁜 도시 (정보 학 올림픽 1 권 통 - T1392)

2302 단어 #정보 학 올림픽그림 이론 - 생 성 트 리
[제목 설명]
도시 C 는 매우 바 쁜 대도시 로 도시 안의 도로 가 매우 붐벼 서 시장 은 그 중의 도 로 를 개조 하기 로 결정 했다.도시 C 의 도 로 는 이렇게 분포 되 어 있다. 도시 에는 n 개의 교차로 가 있 고 어떤 교차로 사이 에는 도로 가 연결 되 어 있 으 며 두 개의 교차로 사이 에는 최대 한 개의 도로 가 연결 되 어 있다.이 도 로 는 양 방향 이 고 모든 교차 로 를 직간 접적 으로 연결 했다.모든 도로 에 하나의 가치 가 있 는데 가치 가 작 을 수록 이 도로 가 바 쁠 수록 개조 가 필요 하 다 는 것 을 나타 낸다.그러나 시 정부의 자금 이 제한 되 어 시장 이 개 조 를 원 하 는 길 은 적 을 수록 좋다. 그래서 그 는 다음 과 같은 요 구 를 했다.
1. 개 조 된 그 도 로 는 모든 교차 로 를 직간 접적 으로 연결 할 수 있다.
2. 요구 1 을 만족 시 키 는 상황 에서 개 조 된 도 로 는 되도록 적다.
3. 요구 1, 2 를 만족 시 키 는 상황 에서 개 조 된 도로 의 최대 치 는 최대한 작다.
시 기획 국 의 당신 으로서 가장 좋 은 결정 을 내 려 야 합 니 다. 그 도 로 를 선택 하면 건설 되 어야 합 니 다.
【 입력 】
첫 번 째 줄 에는 두 개의 정수 n 이 있 는데 m 는 도시 에 n 개의 교차로, m 개의 도로 가 있다 는 것 을 나타 낸다.다음 m 행 은 모든 도로 에 대한 설명 이다. u, v, c 는 교차로 u 와 v 사이 에 도로 가 연결 되 어 있 고 값 은 c 이다.(1≤n≤300，1≤c≤10000)。
【 출력 】
두 개의 정수 s, max 는 당신 이 몇 개의 도 로 를 선 택 했 는 지, 점수 가 가장 큰 도로 의 점수 가 얼마 인지 나타 낸다.
[샘플 입력]
4 5 1 2 3 1 4 5 2 4 7 2 3 6 3 4 8
[출력 사례]
3 6
[원본 프로그램]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 123
#define E 1e-6
using namespace std;
int g[N][N];
int dis[N],vis[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j)
                g[i][j]=0;
            else
                g[i][j]=INF;
        }

    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        g[x][y]=w;
        g[y][x]=w;
    }

    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=g[1][i];
    for(int i=1;i<=n;i++)
    {
        int k;
        int minn=INF;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dis[j]g[k][j])
                dis[j]=g[k][j];
    }

    int maxx=-INF;
    for(int i=1;i<=n;i++)
        maxx=max(maxx,dis[i]);

    cout<

안드로이드 통일된 네트워크 ui 디스플레이 클래스, 통일된 네트워크 관리 클래스
AsyncTask 비동기식 동기화

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage