poj3614 二分图最大匹配 or 贪心-蒲公英云

Sunscreen

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5926		Accepted: 2072

Description

To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they’re at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn’t tan at all……..

The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.

What is the maximum number of cows that can protect themselves while tanning given the available lotions?

Input

* Line 1: Two space-separated integers: C and L
* Lines 2..C+1: Line i describes cow i‘s lotion requires with two integers: minSPFi and maxSPFi
* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri

Output

A single line with an integer that is the maximum number of cows that can be protected while tanning

Sample Input

Sample Output

题意: 给定n个区间, m个值以及这个值对应的数目, 求区间与值的最大匹配;

分析:开始看到n不是太大, 果断想到了用二分图的最大匹配, 只是这个匹配是有数目要求的,

但是变化一下就行了.

#include<bitset>
#include<map>
#include<vector>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#define inf 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline int in()
{
    int res=0;char c;int f=1;
    while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
    while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
const int N=2505;
int n,m,flag,vis[N];
pii a[N],b[N];
vector<int> v[N],match[N]; //match不能定义成数组了, 要用邻接矩阵的形式, 因为每个值可能匹配多个区间
vector<int>::iterator it;
bool dfs(int x)
{
    for(int i=0;i<v[x].size();i++)
    {
        int t=v[x][i];
        if(vis[t]==flag) continue;
        vis[t]=flag;
        if(match[t].size()==0 && b[t].second > 0) //没匹配, 数目也大于0
        {
            match[t].push_back(x);
            b[t].second--;
            return 1;
        }
        if(match[t].size()>0 && b[t].second > 0) //匹配了, 但是数目还是大于0
        {
            match[t].push_back(x);
            b[t].second--;
            return 1;
        }
        if(match[t].size()>0 && b[t].second == 0) //遍历匹配这个值的每个区间, 看是否还有增广路
        {
            for(int j=0;j<match[t].size();j++)
            {
                int y=match[t][j];
                if(dfs(y))
                {
                    match[t].push_back(x);      //有的话 就把这个区间push进去
                    for(it=match[t].begin();;it++)
                    {
                        if(*it==y)
                        {
                            match[t].erase(it);  //同时还要删除让地方的区间
                            break;
                        }
                    }
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        {
            a[i].first=in();
            a[i].second=in();
        }
        for(int i=1;i<=m;i++)
        {
            b[i].first=in();
            b[i].second=in();
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(b[j].first>=a[i].first && b[j].first<=a[i].second)
                {
                    v[i].push_back(j);
                }
            }
        }
        mem(vis,0);
        int ans=0;
        flag=0;
        for(int i=1;i<=n;i++)
        {
            flag=i;
            if(dfs(i)) ans++;
        }
        printf("%d\n",ans);
        for(int i=1;i<=n;i++) v[i].clear(),match[i].clear();
    }
    return 0;
}

贪心策略: 把区间按照左边界排序, 把值按照大小排序, 然后遍历每个值, 把左边界小于当前值的区间全部扔到multiset中, 每次取右边界距离当前的值最近的区间进行贪心,

因为值是逐渐增大的, 右边界越大的区间, 选择也就越大.

#include<bitset>
#include<map>
#include<vector>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#define inf 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline int in()
{
    int res=0;char c;int f=1;
    while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
    while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
const int N=2505;
pii a[N],b[N];
multiset<int > s;
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        s.clear();
        for(int i=0;i<n;i++)
        {
            a[i].first=in();
            a[i].second=in();
        }
        for(int i=0;i<m;i++)
        {
            b[i].first=in();
            b[i].second=in();
        }
        sort(a,a+n);
        sort(b,b+m);
        int ans=0,j=0;
        for(int i=0;i<m;i++)
        {
            for(;j<n && a[j].first<=b[i].first;j++)
            {
                s.insert(a[j].second);
            }
            for(;b[i].second && !s.empty();)
            {
                if(*s.begin() < b[i].first) //如果区间的右边比当前值还要小, 那么直接丢弃, 匹配不了.
                {
                    s.erase(s.begin());
                    continue;
                }
                ans++;
                s.erase(s.begin());  //当前值匹配右边界距离当前值最近的点;
                b[i].second--;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}