SPOJ AMR12A The Black Riders 解題報告

題目

Summer Training 06 - Amritapuri 2012 總結

題意：

有n個人，m個洞，已知每個人到每個洞花的時間。每個洞隻能能容納一個人，但是有人到達之後C時間後就可以容納第二個人（上限是兩個）。求至少K個人躲進洞的最少時間。

題解：

把洞拆成兩個，二分答案mid。如果一個人到某個洞在mid-c前的話，人就連向洞的第一個點，如果在mid前到達的話，就連向第二個點，兩條邊可以共存的。然後跑二分圖，看最大比對。

//Time:380ms
//Memory:2972KB
//Length:1732B
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#define MAXN 110
#define INF 1000000007
using namespace std;
int to[MAXN][MAXN],mlink[MAXN*2];
int n,m,k,c;
bool vis[MAXN];
struct Edge{
    int v,next;
}edge[40005];
int head[MAXN],en;
void init()
{
    en = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    edge[en].v = v;
    edge[en].next = head[u];
    head[u] = en++;
}
bool dfs(int u)
{
    if(vis[u])return 0;
    vis[u] = 1;
    for(int i = head[u]; i!= -1; i=edge[i].next)
    {
        int v = edge[i].v;
        if(mlink[v]==-1||dfs(mlink[v]))
        {
            mlink[v] = u;
            return 1;
        }
    }
    return 0;
}
int solve()
{
    memset(mlink,-1,sizeof(mlink));
    int sum=0;
    for(int i = 0; i < n; i++)
    {
        memset(vis,0,sizeof(vis));
        sum+=dfs(i);
    }
    return sum;
}
bool cal(int mid)
{
    init();
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
        {
            if(to[i][j]<=mid)
                addedge(i,j);
            if(to[i][j]<=mid+c)
                addedge(i,j+MAXN);
        }
    return solve()>=k;
}
int main()
{
    //freopen("/home/moor/Code/input","r",stdin);
    int ncase,ans;
    scanf("%d",&ncase);
    while(ncase--)
    {
        int l=0,mid,r=0,tr=0;
        scanf("%d%d%d%d",&n,&m,&k,&c);
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                scanf("%d",&to[i][j]),tr=max(tr,to[i][j]+c);
        r=tr,l=0;
        while(l<r)
        {
            mid=(l+r)/2;
            if(cal(mid-c))  r=mid;
            else    l=mid+1;
        }
        ans=l;
        printf("%d\n",ans);
    }
    return 0;
}