• Source 
    1. /**************************************************************
    2.     Problem: 2095
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:144 ms
    7.     Memory:984 kb
    8. ****************************************************************/
    9.  
    10. #include <cstdio>
    11. #include <cstring>
    12. #include <algorithm>
    13. #include<queue>
    14. //  by zrt
    15. //  problem:
    16. //  无论你在什么时候开始，重要的是开始以后就不要停止。
    17. using namespace std ;
    18. typedef long long ll ;
    19. const double eps(1e-10) ;
    20. const int inf(0x3fffffff) ;
    21. int n,m;
    22. #define MAX_N 1050
    23. #define MAX_M 2050
    24. int H[MAX_N],X[MAX_M*2],P[MAX_M*2],E[MAX_M*2],tot;
    25. bool vis[MAX_M*2];
    26. int ind[MAX_N],outd[MAX_N];
    27. int minn,maxx;
    28. inline void add(int x,int y,int z){
    29.     P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;
    30. }
    31. int _H[MAX_N],_X[MAX_M*3],_P[MAX_M*3],flow[MAX_M*3],_tot;
    32. inline void _add(int x,int y,int z){
    33.     _P[++_tot]=y;_X[_tot]=_H[x];_H[x]=_tot,flow[_tot]=z;
    34. }
    35. int S,T;
    36. queue<int> q;
    37. int d[MAX_N];
    38. bool bfs(){
    39.     memset(d,0,sizeof d);
    40.     d[S]=1;
    41.     q.push(S);int k;
    42.     while(!q.empty()){
    43.         k=q.front();q.pop();
    44.         for(int i=_H[k];i;i=_X[i]){
    45.             if(flow[i]>0&&!d[_P[i]]){
    46.                 d[_P[i]]=d[k]+1;
    47.                 q.push(_P[i]);
    48.             }
    49.         }
    50.     }
    51.     return d[T];
    52. }
    53. int dfs(int x,int a){
    54.     if(x==T||a==0) return a;
    55.     int f=a,tmp;
    56.     for(int i=_H[x];i&&a;i=_X[i]){
    57.         if(flow[i]>0&&d[x]+1==d[_P[i]]){
    58.             tmp=dfs(_P[i],min(a,flow[i]));
    59.             flow[i]-=tmp;
    60.             flow[i^1]+=tmp;
    61.             a-=tmp;
    62.         }
    63.     }
    64.     if(f==a) d[x]=-1;
    65.     return f-a;
    66. }
    67. int dinic(){
    68.     int maxflow(0);
    69.     while(bfs()) maxflow+=dfs(S,inf);
    70.     return maxflow;
    71. }
    72. bool judge(int limit){
    73.     memset(ind,0,sizeof ind);memset(outd,0,sizeof outd);memset(vis,0,sizeof vis);_tot=1;
    74.     memset(_H,0,sizeof _H);
    75.     for(int i=1;i<=n;i++){
    76.         for(int j=H[i];j;j=X[j]){
    77.             if(E[j]>limit&&E[j^1]>limit) return false;
    78.             if(!vis[j]&&!vis[j^1]&&E[j]<=limit){
    79.                 vis[j]=1;
    80.                 outd[i]++;ind[P[j]]++;
    81.             }
    82.         }
    83.     }
    84.     int fs(0);
    85.     for(int i=1;i<=n;i++){
    86.         if((outd[i]-ind[i])&1) return false;
    87.         if(ind[i]>outd[i]){
    88.             fs+=(ind[i]-outd[i])>>1;
    89.             _add(S,i,(ind[i]-outd[i])>>1);
    90.             _add(i,S,0);
    91.         }else if(ind[i]!=outd[i]){
    92.             _add(i,T,(outd[i]-ind[i])>>1);
    93.             _add(T,i,0);
    94.         }
    95.     }
    96.     for(int i=1;i<=n;i++){
    97.         for(int j=H[i];j;j=X[j]){
    98.             if(!vis[j]&&E[j]<=limit){
    99.                 _add(i,P[j],1);
    100.                 _add(P[j],i,0);
    101.             }
    102.         }
    103.     }
    104.     if(dinic()!=fs) return false ;
    105.     else return true;
    106. }
    107. int main(){
    108.     #ifdef LOCAL
    109.     freopen("in.txt","r",stdin) ;
    110.     freopen("out.txt","w",stdout) ;
    111.     #endif
    112.     scanf("%d%d",&n,&m);
    113.     S=n+1,T=n+2;
    114.     tot=1;
    115.     minn=inf,maxx=-inf;
    116.     for(int i=0,a,b,c,d;i<m;i++){
    117.         scanf("%d%d%d%d",&a,&b,&c,&d);
    118.         minn=min(minn,min(c,d));
    119.         maxx=max(maxx,max(c,d));
    120.         add(a,b,c);add(b,a,d);
    121.     }
    122.     int l=minn-1,r=maxx;
    123.     if(!judge(r)) printf("NIE");
    124.     else{
    125.         int m;
    126.         while(r-l>1){
    127.             m=(l+r)>>1;
    128.             if(judge(m)){
    129.                 r=m;
    130.             }else l=m;
    131.         }
    132.         printf("%d\n",r);
    133.     }
    134.     return 0 ;
    135. }