首页 > ACM题库 > HDU-杭电 > HDU 4406-GPA-最短路径-[解题报告]HOJ
2015
05-24

HDU 4406-GPA-最短路径-[解题报告]HOJ

GPA

问题描述 :

GPA(Grade-Point Average) is one way to measure students’ academic performance in PKU. Each course has an integer credit, ranges from 1 to 99. For each course, you will get a score at the end of the semester, which is an integer ranges from 0 to 100. Then you can calculate the Grade-Point of this course with the following formula. (Your score is x and your Grade-Point is p, using real arithmetic)
Aeroplane chess

Then you can get the GPA with the following formula (the Grade-Point of course i is pi, and the credit of course i is wi).
Aeroplane chess

Now it is not far from the final exam, if you do not review, you can only get a basic score in each course.

You have n days to review. There are K classes in each day. For each class, only one course can be reviewed. After the review, your score in this course will exactly increase by 1. You can get more increment by spending more classes in this course. But the score may not exceed 100.

For some reasons, not any course can be reviewed in any class. Each day you can only review some of the courses.

Now you want your GPA to be as high as possible, and at the same time, you do not want to fail in any course. Please calculate the highest GPA you can get.

输入:

The input consists of several test cases. Each test case begins with 3 integers N (0<=N<=40), K(0<K<=20), M (0<M<=20), representing the number of days, the number of classes in each day and the number of courses. Next line contains M integers representing credits of each course and M integers representing basic scores of each course (0<=score<=100). Next N lines contain an N*M matrix, the jth element in ith row means whether you can review course j in ith day, 1 means you can review course j in ith day, 0 means you cannot. The Input ends with 0 0 0.

输出:

The input consists of several test cases. Each test case begins with 3 integers N (0<=N<=40), K(0<K<=20), M (0<M<=20), representing the number of days, the number of classes in each day and the number of courses. Next line contains M integers representing credits of each course and M integers representing basic scores of each course (0<=score<=100). Next N lines contain an N*M matrix, the jth element in ith row means whether you can review course j in ith day, 1 means you can review course j in ith day, 0 means you cannot. The Input ends with 0 0 0.

样例输入:

2 10 3
1 1 2
50 60 90
1 1 0
1 0 1
2 20 4
1 1 1 1
50 50 50 40
1 1 1 0
0 0 0 1
0 0 0

样例输出:

2.757813
0.000000

这题问题就是当前时刻到底选择哪门课程,易知选择是和分数有关的,并且是一个变化的权值,所以可以用拆点的方式,把从基础分到100分都拆成点,但若这样拆点的话,跑费用流时就必须保证顺序,这样就麻烦了。。观察公式,发现同一门课,分数越高,权值是越低的,所以这是一个单调的,这样的话就可以对每一个分数建一条边,费用流会一条一条的跑。

注意将课程放在X集

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define eps 1e-8
#define MAXN 100
#define MAXM 1000000
#define INF 100000
struct node
{
    int u,v,f,next;
    double c;
}e[MAXM];
int n,k,head[MAXN],pre[MAXN],vis[MAXN];
double dist[MAXN];
int en,s,t,maxflow,mincost,m; //s源点,t汇点
void add(int u,int v,double c,int f)//加边
{
    e[en].u=u;
    e[en].v=v;
    e[en].c=c;
    e[en].f=f;
    e[en].next=head[u];
    head[u]=en++;
    e[en].u=v;
    e[en].v=u;
    e[en].c=-c;
    e[en].f=0;
    e[en].next=head[v];
    head[v]=en++;
}
int spfa()
{
    int i,u,v;
    for(i=0;i<=t;i++)
        pre[i]=-1,vis[i]=0,dist[i]=-INF;
    dist[s]=0;
    vis[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(i=head[u];i!=-1;i=e[i].next)
        {
            v=e[i].v;
            if(e[i].f>0&&dist[u]+e[i].c-eps>dist[v])
            {
                dist[v]=dist[u]+e[i].c;
                pre[v]=i;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
        vis[u]=0;
    }
    if(dist[t]==-INF)
        return 0;
    return 1;
}
void add()
{
    int v;
    int maxf=INF;
    for(v=pre[t];~v;v=pre[e[v].u])
        maxf=min(maxf,e[v].f);
    for(v=pre[t];~v;v=pre[e[v].u])
    {
        e[v].f-=maxf;
        e[v^1].f+=maxf;
        mincost+=maxf*e[v].c;
    }
    maxflow+=maxf;
}
int a[123];
int w[123];
int ADD[123];
int mp[123][123];
void init()
{
    maxflow=0;
    mincost=0;
    s=0;
    t=n+m+1;
    en=0;
    memset(head,-1,sizeof(head));
    memset(ADD,0,sizeof(ADD));
}
double cal(int x,int w)
{
    return (4.0-3.0*(100.0-x)*(100.0-x)/1600.0)*w;
}
int main()
{
    int k,b;
    while(~scanf("%d%d%d",&n,&k,&m))
    {
        if(n+k+m==0) break;
        init();
        for(int i=1;i<=m;i++) scanf("%d",&w[i]);
        for(int i=1;i<=m;i++) scanf("%d",&a[i]);
        for(int i=1;i<=m;i++)
        {
            for(int q=a[i];q<60;q++) add(s,i,INF,1);
            for(int q=max(a[i],60);q<100;q++) add(s,i,cal(q+1,w[i])-cal(q,w[i]),1);
        }
        for(int i=1;i<=n;i++)
        {
            add(m+i,t,0,k);
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&b);
                if(b) add(j,m+i,0,INF);
            }
        }
        while(spfa()) add();
        for(int i=head[s];~i;i=e[i].next)
        {
            if(e[i].v>=1&&e[i].v<=m&&e[i].f==0) ADD[e[i].v]++;
        }
        int ok=1;
        for(int i=1;i<=m;i++)
        {
            if(a[i]+ADD[i]<60)
            {
                ok=0;
                break;
            }
            a[i]+=ADD[i];
        }
        if(ok==0)
        {
            puts("0.000000");
        }
        else
        {
            double ans=0;
            int d=0;
            for(int i=1;i<=m;i++)
            {
                ans+=cal(a[i],w[i]);
                d+=w[i];
            }
            printf("%.6lf\n",ans/d);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/t1019256391/article/details/39736477