首页 > 代码库 > AOJ 2251 Merry Christmas （最小点覆盖）
AOJ 2251 Merry Christmas （最小点覆盖）
【题目链接】 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251
【题目大意】
给出一张图，现在有一些任务，要求在ti时刻送礼物到pi地点
问至少需要几个圣诞老人才能准时完成任务
【题解】
我们将送完一个礼物之后还能赶到下一个地点送礼物的两个点之间连线
只要求出这个图的最小点覆盖就是答案
【代码】
#include <cstdio>#include <algorithm>#include <cstring>#include <vector> #include <queue>using namespace std;const int MAX_V=2000;int V,match[MAX_V];vector<int> G[MAX_V];bool used[MAX_V];void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u);}bool dfs(int v){ used[v]=1; for(int i=0;i<G[v].size();i++){ int u=G[v][i],w=match[u]; if(w<0||!used[w]&&dfs(w)){ match[v]=u; match[u]=v; return 1; } }return 0;}int bipartite_matching(){ int res=0; memset(match,-1,sizeof(match)); for(int v=0;v<V;v++){ if(match[v]<0){ memset(used,0,sizeof(used)); if(dfs(v))res++; } }return res;}void clear(){for(int i=0;i<V;i++)G[i].clear();}const int MAX_N=100;const int MAX_L=1000;const int INF=0x3f3f3f3f;int N,M,L,x,y,z;int d[MAX_N][MAX_N],p[MAX_L],t[MAX_L];void init(){ V=2*L; clear(); memset(d,INF,sizeof(d)); for(int i=0;i<M;i++){ scanf("%d%d%d",&x,&y,&z); d[x][y]=d[y][x]=z; } for(int i=0;i<L;i++)scanf("%d%d",&p[i],&t[i]); for(int k=0;k<N;k++){ d[k][k]=0; for(int i=0;i<N;i++) for(int j=0;j<N;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); }}void solve(){ for(int i=0;i<L;i++) for(int j=0;j<L;j++){ if(i!=j&&t[i]+d[p[i]][p[j]]<=t[j])add_edge(i<<1,j<<1|1); } printf("%d\n",L-bipartite_matching());}int main(){ while(~scanf("%d%d%d",&N,&M,&L),N){ init(); solve(); }return 0;}AOJ 2251 Merry Christmas （最小点覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。