贴板子系列_1-km算法，匈牙利算法

                 1 #include <bits/stdc++.h>
 2#define N 1500
 3#define inf 999999999
 4usingnamespace std;
 5int a[N],bs[N],nx=0,ny=0,k;
 6int linky[N],lx[N],ly[N],slack[N];
 7int visx[N],visy[N],w[N][N];
 8int min(int a,int b){return (a<b)?a:b;}
 9int find(int x){
10     visx[x]=1;
11for(int y=1;y<=ny;y++){
12if(visy[y]) continue;
13int t=lx[x]+ly[y]-w[x][y];
14if(t==0){visy[y]=1;
15if(linky[y]==-1||find(linky[y])){
16                 linky[y]=x;return1;
17            }
18        }
19elseif(slack[y]>t) slack[y]=t;
20    }
21return0;
22}
23int km(){
24     memset(linky,-1,sizeof(linky));
25     memset(ly,0,sizeof(ly));
26for(int i=1;i<=nx;i++) lx[i]=-inf;
27for(int i=1;i<=nx;i++)for(int j=1;j<=ny;j++)if(w[i][j]>lx[i])lx[i]=w[i][j];
28for(int x=1;x<=nx;x++){
29for(int i=1;i<=ny;i++)
30             slack[i]=inf;
31while(1){
32             memset(visx,0,sizeof(visx));
33             memset(visy,0,sizeof(visy));
34if(find(x)) break;
35int d=inf;
36for(int i=1;i<=ny;i++) if(!visy[i]&&d>slack[i]) d=slack[i];
37for(int i=1;i<=nx;i++) if(visx[i]) lx[i]-=d;
38for(int i=1;i<=ny;i++) if(visy[i]) ly[i]+=d; else slack[i]-=d;
39        }
40    }
41int result=0;
42for(int i=1;i<=ny;i++)
43if(linky[i]>-1) result+=w[linky[i]][i];
44return result;
45}
46int main(){
47     scanf("%d%d%d",&nx,&ny,&k);
48for(int i=1;i<=k;i++){
49int a,b,c;scanf("%d%d%d",&a,&b,&c);
50         w[a][b]=c;
51     }printf("%d\n",km());
52return0;
53 }

                 1 #include <cstdio>
 2 #include <cstring>
 3#define N 1010
 4usingnamespace std;
 5int map[N][N];
 6int max,x1,m,y1,tot,ans;
 7int used[N],link[N];
 8int find(int t)
 9{
10for(int i=1;i<=y1;i++)
11    {
12if(used[i]==0&&map[t][i]==1)
13        {
14             used[i]=1;
15if(link[i]==0||find(link[i]))
16            {
17                 link[i]=t;
18return1;
19            }
20        }
21    }
22return0;
23}
24int main()
25{
26     scanf("%d%d%d%d",&max,&x1,&y1,&m);
27     max++;tot=x1+y1;
28for(int i=1;i<=m;i++)
29    {
30int a,b;
31         scanf("%d%d",&a,&b);
32         map[a][b]=1;
33    }
34for(int i=1;i<=y1;i++)link[i]=0;
35for(int i=1;i<=x1;i++)
36    {
37for(int i=1;i<=y1;i++) used[i]=0;
38if(find(i))
39             ans++;
40    }
41     printf("%d\n",(max<tot-ans)? max:tot-ans);
42return0;
43 }