题意：
给出一张二分图，初始每个节点的度数都为零。选择若干条边，使得每个节点的度数范围再[L,R]范围内。每选一条边，边上两端的节点度数+1。
题解：
首先先学习什么是有上下界的网络流
源点与左边每个节点连[L,R]的边。右边每个节点与汇点连[L,R]的边。
左右两边按照题意连权值为1的边。
最后判断有无可行流即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=70005;
int sp,tp,cnt=1,head[maxn],nxt[maxn],to[maxn],cap[maxn],dis[1005],st,de,def[maxn],m,n,k;
inline int read(){
int ans=0; char last=' ',ch=getchar();
while(ch<'0' || ch>'9')last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans; return ans;
}
inline void addedge(int u,int v,int p){
nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,cap[cnt]=p;
nxt[++cnt]=head[v],head[v]=cnt,to[cnt]=u,cap[cnt]=0;
}
inline bool bfs(){
int u,e,v;
queue<int> que;
memset(dis,-1,sizeof(dis));
que.push(sp),dis[sp]=0;
while(!que.empty()){
u=que.front(),que.pop();
for(int e=head[u];e;e=nxt[e]){
if(cap[e]>0&&dis[v=to[e]]==-1){
dis[v]=dis[u]+1,que.push(v);
if(v==tp) return true;
}
}
}
return false;
}
inline int dfs(const int &u,const int &flow){
if(u==tp) return flow;
int res=0,v,flw;
for(int e=head[u];e;e=nxt[e]){
if(cap[e]>0&&dis[u]<dis[v=to[e]]){
flw=dfs(v,min(cap[e],flow-res));
if(flw==0) dis[v]=-1;
cap[e]-=flw,cap[e^1]+=flw;
res+=flw;if(res==flow) break;
}
}
return res;
}
inline int dinic(int sp,int tp){
int ans=0;
while(bfs()) {
ans+=dfs(sp,1<<30);
}
return ans;
}
int main(){
int k,cas=0;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
cas++;
int s,t,up,down,sum=0;
cnt=1;
memset(def,0,sizeof(def));
memset(head,-1,sizeof(head));
down=read() , up=read();
st=n+m+1,de=n+m+2;
for(int i=1;i<=n;i++){
addedge(st,i,up-down);
def[st]+=down,def[i]-=down;
}
for(int i=1 ; i<=m ; i++)
{
addedge(i+n,de,up-down);
def[i+n]+=down,def[de]-=down;
}
for(int i=1 ; i<=k ; i++)
{
scanf("%d%d",&s,&t);
addedge(s,t+n,1);
}
sp=n+3+m,tp=n+4+m;
for(int i=1;i<=n+m+2;i++){
if(def[i]>0) sum+=def[i],addedge(i,tp,def[i]);
if(def[i]<0) addedge(sp,i,-def[i]);
}
addedge(de,st,1<<30);///变无源
printf("Case %d: ",cas);
if(dinic(sp,tp)==sum){
cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;
}
return 0;
}
还有一种贪心的算法，据说是数据太水可以过 ， :贪心地删边后检查每个点的度即可
#include<stdio.h> #include<string.h> struct no { int u,v; }a[40001]; int sum[40001]; int main( ) { int n,m,k,L,R,cnt,cas=0; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { memset(sum,0,sizeof(sum)); cnt=0; scanf("%d%d",&L,&R); for(int i=1 ; i<=k ; i++) { int u,v; scanf("%d%d",&u,&v); v+=n; a[cnt].u=u; a[cnt++].v=v; sum[u]++; sum[v]++; } for(int i=0 ; i<cnt ; i++) { if(sum[a[i].u]>R || sum[a[i].v]>R) { sum[a[i].u]--; sum[a[i].v]--; } } bool fa=0; for(int i=1 ; i<=n+m ; i++) { if(sum[i]<L||sum[i]>R) { fa=1; break; } } cas++; printf("Case %d: ",cas); if(fa) puts("No"); else puts("Yes"); } }