题解 P3529 【[POI2011]PRO-Programming Contest】

· · 题解

最大流

（罚时：每道题被完成的 时间点 之和）

先不看罚时最小的要求，只考虑做题数量最多，可以像这样建图：

1 每个人连向自己会做的题，由于一个人只会做一道题一次，所以容量为1

2 每道题连向汇点，由于一道题只需要被做一次，所以容量为1

3 源点连向每个人，由于每个人最多的做题数为t/r，所以容量填t/r

最大流就是最大做题数

再考虑罚时最小，就是要求从比赛开始，要尽可能更多人在做题，上面这种建图的缺陷在于可能一个人包揽了很多题，导致罚时很大（明明他可以让别人做一些）导致这种为题就在于源点向人连的边容量过大，一开始允许他做很多题。

所以可以动态加边，每次加一组源点到人的容量为1的边，慢慢开放他们做题的权限，防止一个人疯狂做题，直到某一次即使加边他们也做不出更多的题目，目前的流量图就是一个合法的方案。

输出方案：对于每条人到题目正向边，如果被流满则这个人做了这道题。

#include<bits/stdc++.h>
#define N 500000
#define inf 1000000007
using namespace std;
int n,m,r,t,k,first[N],nxt[N],tot=1,S,T;
int in1[N],in2[N],depth[N],maxflow=0,flow,max_num,last=0,ans=0;
int ans1[N],ans2[N],ans3[N],tpp=0,p[N]={0};
queue <int> q;
struct Edge
{
    int u,v,flow;
}edge[N];
void Add(int u,int v,int flow)
{
    tot++;
    nxt[tot]=first[u];
    first[u]=tot;
    edge[tot]=(Edge){u,v,flow};
    return;
}
void Addedge(int u,int v,int flow)
{
    Add(u,v,flow);
    Add(v,u,0);
    return;
}
int bfs()
{
    memset(depth,0,sizeof(depth));
    while (q.size()) q.pop();
    depth[S]=1;
    q.push(S);
    while (q.size())
    {
        int tmp=q.front();
        q.pop();
        for (int j=first[tmp];j!=-1;j=nxt[j])
            if (edge[j].flow&&!depth[edge[j].v])
            {
                int to=edge[j].v;
                depth[to]=depth[tmp]+1;
                q.push(to);
            }
    }
    if (depth[T]) return 1;
    else return 0;
}
int Dinic(int p,int f)
{
    if (p==T) return f;
    int k,rest=f;
    for (int j=first[p];j!=-1&&rest;j=nxt[j])
         if (edge[j].flow&&depth[edge[j].v]==depth[p]+1)
         {
            int to=edge[j].v;
            k=Dinic(to,min(rest,edge[j].flow));
            if (!k) 
            {
                depth[to]=0;
                continue;
            }
            edge[j].flow-=k;
            edge[j^1].flow+=k;
            rest-=k;
         }
    return f-rest;
}
int main()
{
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    memset(first,-1,sizeof(first));
    scanf("%d%d%d%d%d",&n,&m,&r,&t,&k);
    S=n+m+1;
    T=n+m+2;
    for (int i=1;i<=k;i++) scanf("%d%d",&in1[i],&in2[i]);
    for (int i=1;i<=k;i++) Addedge(in1[i],in2[i]+n,1);
    for (int i=n+1;i<=n+m;i++) Addedge(i,T,1);
    max_num=t/r;
    for (int i=1;i<=max_num;i++)
    {
        for (int i=1;i<=n;i++) Addedge(S,i,1);
        while (bfs())
            while ((flow=Dinic(S,inf))) maxflow+=flow;
        if (maxflow==last) break;
        last=maxflow;
    }
    for (int i=2;i<=tot;i+=2)
    {
        int p1=edge[i].u,p2=edge[i].v;
        if (edge[i].flow==0&&p1!=S&&p2!=T&&i%2==0)
        {
            tpp++;
            ans1[tpp]=p1;
            ans2[tpp]=p2-n;
            ans3[tpp]=p[p1]*r;
            p[p1]++;
            ans+=ans3[tpp]+r;
        }
    }
    printf("%d %d\n",maxflow,ans);
    for (int i=1;i<=tpp;i++) printf("%d %d %d\n",ans1[i],ans2[i],ans3[i]);
//  for (int i=2;i<=tot;i+=2) printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].flow);
    return 0;
}