程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4406 GPA 最大費用最大流

hdu 4406 GPA 最大費用最大流

編輯：C++入門知識

hdu 4406 GPA 最大費用最大流

題意：給定n,k,m分別代表天數，每天上的課，以及科目數。

給定每門課的學分，已經基礎分數。

給定n天每天有哪些課能學。

求如何安排復習，使得GPA盡可能大且沒有掛科，算出GPA。

思路：最大費用最大流。定義函數f(score,credit)=credit×(4-3.0/1600×(100-score)^2）。每一天向匯點連邊,容量為k,費用0; 每門課

與每天根據是否在當天能上連邊，容量為k，費用為0; 源點向每門課連邊,若基礎分score小於60,則與源點連一條流量60-score、費用

inf的邊，保證優先到達60，接著從源點與該課程連40條流量分別為1,費用為f(x+1,)-f(x,p)的邊（40條代表61到100）;若基礎分score

大於等於60，則連100-score條容量1、費用f(x+1,p)-f(x,p)的邊。跑完最大費用最大流之後，再看是否還有哪門課不及格，如果有ans=0,不然計算GPA。詳見代碼：

/*********************************************************
  file name: hdu4406.cpp
  author : kereo
  create time:  2015年02月11日 星期三 15時35分08秒
*********************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair
#define mk(x,y) make_pair((x),(y))
int n,m,k,edge_cnt;
double d[N];
int head[N],inq[N],pre[N],A[N],w[N],score[N];
struct Edge{
    double cost;
    int v,cap,flow,next;
}edge[MAXN];
void init(){
    edge_cnt=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,double cost){
    edge[edge_cnt].v=v; edge[edge_cnt].cap=cap; edge[edge_cnt].flow=0; 
    edge[edge_cnt].cost=cost; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;
    edge[edge_cnt].v=u; edge[edge_cnt].cap=0; edge[edge_cnt].flow=0;
    edge[edge_cnt].cost=-cost; edge[edge_cnt].next=head[v]; head[v]=edge_cnt++;
}
bool spfa(int st,int ed,int &flow,double &cost){
    memset(inq,0,sizeof(inq));
    for(int i=0;i<=ed;i++) d[i]=-1.0*inf;
    d[st]=0; inq[st]=1; pre[st]=st; A[st]=inf;
    queueQ;
    Q.push(st);
    while(!Q.empty()){
        int u=Q.front(); Q.pop();
        inq[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            if(edge[i].cap>edge[i].flow && d[v]