首页 > ACM题库 > HDU-杭电 > hdu 2362 Contest-最小生成树-[解题报告]C++
2014
01-05

hdu 2362 Contest-最小生成树-[解题报告]C++

Contest

问题描述 :

You and your team are participating in a programming contest. After reading all problems, you have estimated for each problem how long it will take you to solve it. Your teammates have done exactly the same. Now you want to divide the problems, so that the total number of solved problems will be maximized.
Your team is very organized and each team member always writes down all the details on paper. Therefore the computer never forms a bottleneck. The only constraint is that for each team member, the total time required to solve the problems assigned to him should not exceed the time left in the contest.

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers n (1 <= n <= 10) and m (1 <= m <= 300). The number of problems and the number of minutes left in the contest.

Three lines with n integers each. Each line describes the solving times for a different team member. The jth integer on the ith line is denoted by sij : either the time in minutes it takes the ith person to solve the jth problem (1 <= sij <= 300), or -1 if the person cannot solve this problem.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers n (1 <= n <= 10) and m (1 <= m <= 300). The number of problems and the number of minutes left in the contest.

Three lines with n integers each. Each line describes the solving times for a different team member. The jth integer on the ith line is denoted by sij : either the time in minutes it takes the ith person to solve the jth problem (1 <= sij <= 300), or -1 if the person cannot solve this problem.

样例输入:

1
10 300
10 60 -1 -1 10 10 10 240 1 30
15 -1 30 -1 60 60 60 300 5 250
20 -1 -1 60 60 90 90 300 2 245

样例输出:

10

刘汝佳新书–训练指南

题意:你需要花费不超过cost元来搭建一个比赛网络。网络中有n台机器,编号0~n-1,其中机器0为服务器,其他机器为客户机。一共有m条可以使用的网线,其中第i条网线的发送端是机器ui,接收端是机器vi(数据只能从机器ui单向传输到机器vi),带宽是bi Kbps,费用是ci元。每台客户机应当恰好从一台机器接收数据。你的任务是最大化网络中的最小带宽。

分析:最小树形图,然后二分答案最小带宽。

// File Name: 11865.cpp
// Author: zlbing
// Created Time: 2013/2/17 22:36:04

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define MAXN 205
struct Edge{
    int from,to,dist,band;
}edges[MAXN*MAXN];
int In[MAXN];
int pre[MAXN],ID[MAXN],vis[MAXN];
bool Directed_MST(int root,int n,int m,int C,int B)
{
    long long ans=0;
    while(true)
    {
        //1、找最小入边
        for(int i=0;i<n;i++)In[i]=INF;
        for(int i=0;i<m;i++)
        {
            int u=edges[i].from;
            int v=edges[i].to;
            if(edges[i].dist<In[v]&&u!=v&&edges[i].band>=B)
            {
                pre[v]=u;
                In[v]=edges[i].dist;
            }
        }
        //2、判断是否有最小生成树
        for(int i=0;i<n;i++)
        {
            if(i==root)continue;
            if(In[i]==INF)return false;
        }
        //3、找环
        int cntnode=0;
        CL(ID,-1);
        CL(vis,-1);
        In[root]=0;
        for(int i=0;i<n;i++)
        {
            ans+=In[i];
            int v=i;
            while(vis[v]!=i&&ID[v]==-1&&v!=root)
            {
                vis[v]=i;
                v=pre[v];
            }
            if(v!=root&&ID[v]==-1)
            {
                for(int u=pre[v];u!=v;u=pre[u])
                {
                    ID[u]=cntnode;
                }
                ID[v]=cntnode++;
            }
        }
        if(cntnode==0)break;
        for(int i=0;i<n;i++)
            if(ID[i]==-1)
                ID[i]=cntnode++;
        //4、缩点,重新标记
        for(int i=0;i<m;i++)
        {
            int v=edges[i].to;
            edges[i].from=ID[edges[i].from];
            edges[i].to=ID[edges[i].to];
            if(edges[i].from!=edges[i].to)
            {
                edges[i].dist-=In[v];
            }
        }
        n=cntnode;
        root=ID[root];
    }
    if(ans<=C)
    return true;
    else return false;
}
int main(){
    int T;
    scanf("%d",&T);
    int N,M,C;
    while(T--)
    {
        scanf("%d%d%d",&N,&M,&C);
        int a,b,c,d;
        int maxn=0,minn=INF;
        for(int i=0;i<M;i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            edges[i].from=a;
            edges[i].to=b;
            edges[i].band=c;
            edges[i].dist=d;
            edges[i+M].from=a;
            edges[i+M].to=b;
            edges[i+M].band=c;
            edges[i+M].dist=d;
            maxn=max(maxn,c);
            minn=min(minn,c);
        }
        if(Directed_MST(0,N,M,C,minn)==false)
            printf("streaming not possible.\n");
        else{
            int L=minn,R=maxn;
            while(L<R)
            {
                int mid=L+(R-L+1)/2;
                for(int i=0;i<M;i++)
                edges[i]=edges[i+M];
                if(!Directed_MST(0,N,M,C,mid))
                    R=mid-1;
                else L=mid;
            }
            printf("%d kbps\n",L);
        }
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/arbitrary/archive/2013/02/17/2915073.html