• Source 
    1. /**************************************************************
    2.     Problem: 1532
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:576 ms
    7.     Memory:2764 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. //by zrt
    14. //problem:
    15. using namespace std;
    16. typedef long long ll;
    17. const double eps(1e-10);
    18. int n,m;
    19. int H[20005],X[110005],P[110005],flow[110005],d[20005],tot;
    20. int q[20005],h,t;
    21. int a[10005],b[10005];
    22. int S,T;
    23. inline void add(int x,int y,int z){
    24.     P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
    25. }
    26. bool bfs(){
    27.     memset(d,0,sizeof d);h=t=0;
    28.     d[S]=1;q[t++]=S;
    29.     int k;
    30.     while(h!=t){
    31.         k=q[h++];
    32.         for(int i=H[k];i;i=X[i]){
    33.             if(flow[i]>0&&(!d[P[i]])){
    34.                 q[t++]=P[i];
    35.                 d[P[i]]=d[k]+1;
    36.             }
    37.         }
    38.     }
    39.     return d[T];
    40. }
    41. int dfs(int x,int a){
    42.     if(a==0||x==T) return a;
    43.     int f=a,tmp;
    44.     for(int i=H[x];i&&a;i=X[i]){
    45.         if(d[P[i]]==d[x]+1&&flow[i]>0){
    46.             tmp=dfs(P[i],min(a,flow[i]));
    47.             a-=tmp;
    48.             flow[i]-=tmp;
    49.             flow[i^1]+=tmp;
    50.         }
    51.     }
    52.     if(f==a) d[x]=-1;
    53.     return f-a;
    54. }
    55. int dinic(){
    56.     int f(0);
    57.     while(bfs()){
    58.         f+=dfs(S,1<<30);
    59.     }
    60.     return f;
    61. }
    62. bool judge(int x){
    63.     memset(H,0,sizeof H);tot=1;
    64.     for(int i=0;i<m;i++){
    65.         add(S,i,1);add(i,S,0);
    66.         add(i,a[i]+m,1);add(a[i]+m,i,0);
    67.         add(i,b[i]+m,1);add(b[i]+m,i,0);
    68.     }
    69.     for(int i=1;i<=n;i++) add(i+m,T,x),add(T,i+m,0);
    70.     if(dinic()>=m) return true;
    71.     else return false;
    72. }
    73. int main(){
    74.     #ifdef LOCAL
    75.     freopen("in.txt","r",stdin);
    76.     freopen("out.txt","w",stdout);
    77.     #endif
    78.     scanf("%d%d",&n,&m);
    79.     for(int i=0;i<m;i++){
    80.         scanf("%d%d",&a[i],&b[i]);
    81.     }
    82.     int L(0),R(m),M;
    83.     S=20003,T=20004;
    84.     while(R-L>1){
    85.         M=(L+R)>>1;
    86.         if(judge(M)){
    87.             R=M;
    88.         }else L=M;
    89.     }
    90.     printf("%d\n",R);
    91.     return 0;
    92. }