题目连接:

  https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4899

题意:

  给你n,m,m对关系

  m次输入,a,b,表示a喜欢b的书

  问你在随意安排数的情况下,是否每个人都能得到自己想要的书

题解:

  也就是最大匹配数量,可以用最大流求或者匈牙利 

 每本书只能用一次,建边S-a a'-T

  有关系 a - b'

  建图,跑最大流

#include <cstdio>
#include <cstring>
#include <vector>
#include<iostream>
#include <algorithm>
using namespace std;
namespace NetFlow
{
const int MAXN=,MAXM=,inf=1e9;
struct Edge
{
int v,c,f,nx;
Edge() {}
Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
} E[MAXM];
int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
void init(int _n)
{
N=_n,sz=; memset(G,-,sizeof(G[])*N);
}
void link(int u,int v,int c)
{
E[sz]=Edge(v,c,,G[u]); G[u]=sz++;
E[sz]=Edge(u,,,G[v]); G[v]=sz++;
}
int ISAP(int S,int T)
{//S -> T
int maxflow=,aug=inf,flag=false,u,v;
for (int i=;i<N;++i)cur[i]=G[i],gap[i]=dis[i]=;
for (gap[S]=N,u=pre[S]=S;dis[S]<N;flag=false)
{
for (int &it=cur[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[u]==dis[v=E[it].v]+)
{
if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f;
pre[v]=u,u=v; flag=true;
if (u==T)
{
for (maxflow+=aug;u!=S;)
{
E[cur[u=pre[u]]].f+=aug;
E[cur[u]^].f-=aug;
}
aug=inf;
}
break;
}
}
if (flag) continue;
int mx=N;
for (int it=G[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[E[it].v]<mx)
{
mx=dis[E[it].v]; cur[u]=it;
}
}
if ((--gap[dis[u]])==) break;
++gap[dis[u]=mx+]; u=pre[u];
}
return maxflow;
}
bool bfs(int S,int T)
{
static int Q[MAXN]; memset(dis,-,sizeof(dis[])*N);
dis[S]=; Q[]=S;
for (int h=,t=,u,v,it;h<t;++h)
{
for (u=Q[h],it=G[u];~it;it=E[it].nx)
{
if (dis[v=E[it].v]==-&&E[it].c>E[it].f)
{
dis[v]=dis[u]+; Q[t++]=v;
}
}
}
return dis[T]!=-;
}
int dfs(int u,int T,int low)
{
if (u==T) return low;
int ret=,tmp,v;
for (int &it=cur[u];~it&&ret<low;it=E[it].nx)
{
if (dis[v=E[it].v]==dis[u]+&&E[it].c>E[it].f)
{
if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
{
ret+=tmp; E[it].f+=tmp; E[it^].f-=tmp;
}
}
}
if (!ret) dis[u]=-; return ret;
}
int dinic(int S,int T)
{
int maxflow=,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G[])*N);
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
}
using namespace NetFlow;
int n,m;
int main(){
while(~scanf("%d%d", &n, &m)) {
init();
int S = *n+, T = *n+;
for(int i = ; i < m; i++) {
int r, c;
scanf("%d%d", &r, &c);
r++;c++;
link(c,r+n,);
}
for(int i=;i<=n;i++) {
link(S,i,);
link(i+n,T,);
}
int ans = dinic(S,T);
if(ans == n) puts("YES");
else puts("NO");
}
return ;
}

最新文章

  1. 李洪强iOS经典面试题154- 通知与推送
  2. 自定义BadgeView
  3. C++库(Thrift)
  4. ExtJS笔记 Ext.Loader
  5. 从0到1---“保多多”APP的开发(二)
  6. 理解 Soap
  7. 迷宫问题(bfs的应用)
  8. OPENSSL安装 以及使用openssl中的AES加密和解密
  9. OC基础12:数字、字符串和集合1
  10. 【m从翻译os文章】写日志禁令Sqlnet.log和Listener.log
  11. Web安全知多少
  12. Rolling Hash(Rabin-Karp算法)匹配字符串
  13. CentOS下redis集群安装
  14. Python中使用MongoEngine1
  15. day 7-22 进程,线程,协程
  16. 微信小程序上传图片,视频及预览
  17. Ubuntu16.04 64位编译安装Hi3520D_SDK_V1.0.4.0
  18. u-boot之ARM920T的start.S分析
  19. Cross-platform Tools
  20. openvpn之EasyRSA配置篇

热门文章

  1. 用开源Look&amp;Feel (Substance)写 漂亮的Swing应用程序
  2. JavaScript 实现鼠标拖动元素
  3. smb
  4. Mysql性能监控
  5. [Effective JavaScript 笔记]第15条:当心局部块函数声明笨拙的作用域
  6. 快速诊断Linux性能
  7. Kalendar server Beijing Tiandiyuandian Technology Limited 果然是木马
  8. 使用Cydia Substrate 从Native Hook Android Java世界
  9. 【数据库】如家汉庭酒店2000万开房数据1.71G/BAK,792M/CSV
  10. &amp;&amp;队友最近一周水水