ZHOJ-1100 [网络流]飞行员配对方案问题 (+USACO-4.2.1)
窝才不说这应该是二分图匹配然而窝用网络流的板子过掉了。。。
为了对得起标题边上的网络流和老早以前做过的一道纯网络流的题目,窝又无聊地做了一遍纯网络流。
要设定一个超级源点和超级汇点,然而这并没有什么难度。
直接上代码吧
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <queue> using namespace std; queue <int> que; int NM,n,m,x,y,ans; int pre[500],flow[500]; int road[500][500]; int BFS(int xx,int yy) { while (!que.empty()) que.pop(); for (int i=1;i<=NM+2;++i) pre[i]=-1; que.push(xx); pre[xx]=0,flow[xx]=0x7fffffff; while (!que.empty()) { int h=que.front(); que.pop(); if (h==yy) break; for (int i=1;i<=NM+2;++i) { if (i!=xx && road[h][i]>0 && pre[i]==-1) { que.push(i); flow[i]=min(flow[h],road[h][i]); pre[i]=h; } } } if (pre[yy]==-1) return -1; else return flow[yy]; } int MAX_FLOW(int xx,int yy) { int sum=0; int minn=0; while ((minn=BFS(xx,yy))!=-1) { int k=yy; while (k!=xx) { int la=pre[k]; road[la][k]-=1; road[k][la]+=1; k=la; } sum+=minn; } return sum; } int main() { freopen("1100.in","r",stdin); freopen("1100.out","w",stdout); scanf("%d%d",&m,&n); memset(road,0,sizeof(road)); scanf("%d%d",&x,&y); while (x!=-1 && y!=-1) { road[x][y]=1; scanf("%d%d",&x,&y); } NM=n+m; for (int i=1;i<=m;++i) road[NM+1][i]=1; for (int i=m+1;i<=n;++i) road[i][NM+2]=1; ans=MAX_FLOW(NM+1,NM+2); if (ans==0) printf("No Solution!"); else printf("%d\n",ans); _fcloseall(); return 0; }
算了,还是不吐槽第一遍写网络流的线段树大师吧
PS. USACO上也有一道水水的,标号为4.2.1(有木有感觉两段代码基本上一模一样哎)
附上代码
/* ID: lujiaxi1 PROG: ditch LANG: C++ */ #include <iostream> #include <cstdio> #include <cstring> #include <climits> #include <queue> #define maxn 201 using namespace std; int ca[maxn][maxn],pre[maxn],flow[maxn]; int n,m; queue<int> que; int BFS(int a,int b) { while (!que.empty()) que.pop(); for (int i=1;i<=m;++i) { pre[i]=-1; } pre[a]=0; flow[a]=INT_MAX; que.push(a); while (!que.empty()) { int k=que.front(); que.pop(); if (k==b) break; for (int i=1;i<=m;++i) { if (i!=a && ca[k][i]>0 && pre[i]==-1) { pre[i]=k; flow[i]=min(ca[k][i],flow[k]); que.push(i); } } } if (pre[b]==-1) return -1; else return flow[b]; } int MAX_flow(int a,int b) { int sum=0; int minn=0; while ((minn=BFS(a,b))!=-1) { int k=b; while (k!=a) { int la=pre[k]; ca[la][k]-=minn; ca[k][la]+=minn; k=la; } sum+=minn; } return sum; } int main() { freopen("ditch.in", "r", stdin); freopen("ditch.out", "w", stdout); cin>>n>>m; for (int i=1;i<=n;++i) { int a,b,c; cin>>a>>b>>c; ca[a][b]+=c; } cout<<MAX_flow(1,m)<<endl; fclose(stdin); fclose(stdout); return 0; }
2022年8月27日 15:23
Central Board of Secondary Education (CBSE) is Going to Conduct 11th or 12th Examination in the month of March to April 2023 Under Union Government of India. CBSE Published in the Class 12th Examination Model Question CBSE 11th Question Paper Paper 2023 Blueprint at Official Website Central Board of Secondary Education (CBSE) is Going to Conduct 11th or 12th Examination in the month of March to April 2023 Under Union Government of India. CBSE Published in the Class 12th Examination Model Question Paper 2023 Blueprint at Official Website