题目链接:http://codeforces.com/gym/101873/problem/F
题意:有n个插孔,m个机器,和一个插板,一个插孔可以连接一个机器,插板可以使一个插孔连接三个机器,找到最大的连接数
当时第一眼觉得是网络流的题目,因为看过类似的题目,他是有k个插板,但是一个插板可以使插孔多连接一个机器。这题特殊在于只有一个插板,那我们先只考虑没有插板的情况下,找到最大匹配,然后再对n个插孔寻找增广路,找到最大的匹配值
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1500+10; const int maxm = 75000+10; const int mod=1e9+7; int f[maxn],to[maxm],nex[maxm],cnt,match[maxn],match2[maxn],vis[maxn]; int n,m,k; void add(int a,int b) { cnt++; to[cnt]=b; nex[cnt]=f[a]; f[a]=cnt; } int dfs(int x) { for(int i=f[x];i;i=nex[i]) { int v=to[i]; if(!vis[v]) { vis[v]=1; if(!match[v]||dfs(match[v])) { match[v]=x; return 1; } } } return 0; } int main() { ll ans=0; cin>>n>>m>>k; for(int i=1;i<=k;i++) { int a,b; scanf("%d %d",&a,&b); add(a,b); } for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } for(int i=1;i<=m;i++)match2[i]=match[i]; ll maxx=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)match[j]=match2[j]; ll x=0; for(int j=1;j<=2;j++) { memset(vis,0,sizeof(vis)); if(dfs(i))x++; } maxx=max(maxx,x); } cout<<ans+maxx<<endl; return 0; }