题意:
有C头牛,每头牛有它可以接受的药的最小值和最大值,有L瓶药,每瓶药有一个值u和它最多能给v头牛用,求最多有多少头牛能满足。
分析:
网络流或二分图多重匹配或优先队列,这道题优化了我的dinic模板,原来的模板会TLE。。。
代码:
//poj 3614
//sep9
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int maxN=5005;
const int maxM=1000002;struct Edge
{int v,f,nxt;
}e[maxM*2+10];
queue<int> que;
int src,sink;
int g[maxN+10];
int nume;
bool vis[maxN+10];
int dist[maxN+10];
pair<int,int> a[2505];
void addedge(int u,int v,int c)
{e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume;e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume;
}void init()
{memset(g,0,sizeof(g)); nume=1;
}int bfs()
{while(!que.empty()) que.pop();memset(dist,0,sizeof(dist));memset(vis,0,sizeof(vis));vis[src]=true;que.push(src); while(!que.empty()){int u=que.front();que.pop();for(int i=g[u];i;i=e[i].nxt)if(e[i].f&&!vis[e[i].v]){que.push(e[i].v);dist[e[i].v]=dist[u]+1;vis[e[i].v]=true; if(e[i].v==sink)return 1;}}return 0;
}int dfs(int u,int delta)
{if(u==sink)return delta;int ret=0;for(int i=g[u];ret<delta&&i;i=e[i].nxt)if(e[i].f&&dist[e[i].v]==dist[u]+1){int dd=dfs(e[i].v,min(e[i].f,delta-ret));if(dd>0){e[i].f-=dd;e[i^1].f+=dd;ret+=dd;}elsedist[e[i].v]=-1;} return ret;
}int dinic()
{int ret=0;while(bfs()==1)ret+=dfs(src,INT_MAX);return ret;
}int main()
{int i,j,C,L; init(); scanf("%d%d",&C,&L);src=0,sink=C+L+1;for(i=1;i<=C;++i){int u,v;scanf("%d%d",&u,&v);a[i]=make_pair(u,v);addedge(src,i,1);}sort(a+1,a+1+C);for(i=1;i<=L;++i){int u,v;scanf("%d%d",&u,&v);for(j=1;j<=C;++j)if(a[j].first<=u&&u<=a[j].second)addedge(j,C+i,1); else if(a[j].first>u)break; addedge(C+i,sink,v);}printf("%d",dinic()); return 0;
}