YYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承受的最大风力最小的路线。

输入：第一行为两个用空格隔开的整数n（2<=n<=1000），m(1<=m<=2000)，接下来读入m行由空格隔开的4个整数a，b（1<=a,b<=n,a<>b），c，d(1<=c,d<=1000)，表示第i+1行第i座桥连接小岛a和b，从a到b承受的风力为c，从b到a承受的风力为d。

输出：如果无法完成减肥计划，则输出NIE，否则第一行输出承受风力的最大值（要使它最小)

注意：通过桥为欧拉回路

  1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #include<cstdio>  5 #include<cmath>  6 #include<vector>  7 #include<queue>  8 using namespace std;  9 const int INF=0x3f3f3f3f; 10 const int mxn=2010; 11 int read(){ 12     int x=0,f=1;char ch=getchar(); 13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15     return x*f; 16 } 17 struct edge{ 18     int v,nxt,f; 19 }e[mxn<<2]; 20 int hd[mxn],mct=0; 21 void add_edge(int u,int v,int w){ 22     e[++mct].nxt=hd[u];e[mct].v=v;e[mct].f=w;hd[u]=mct;return; 23 } 24 void insert(int u,int v,int w){ 25     add_edge(u,v,w); 26     add_edge(v,u,0); 27 } 28 int n,m,S,T; 29 int d[mxn]; 30 bool BFS(){ 31     memset(d,0,sizeof d); 32     queue<int>q; 33     q.push(S);d[S]=1; 34     while(!q.empty()){ 35         int u=q.front();q.pop(); 36         for(int i=hd[u];i;i=e[i].nxt){ 37             int v=e[i].v; 38             if(!e[i].f || d[v])continue; 39             d[v]=d[u]+1; 40             q.push(v); 41         } 42     } 43     return d[T]; 44 } 45 int DFS(int u,int lim){ 46     if(u==T)return lim; 47     int f=0,tmp; 48     for(int i=hd[u];i;i=e[i].nxt){ 49         int v=e[i].v; 50         if(d[v]==d[u]+1 && e[i].f && (tmp=DFS(e[i].v,min(lim,e[i].f)))){ 51             e[i].f-=tmp; 52             e[i^1].f+=tmp; 53             f+=tmp; 54             lim-=tmp; 55             if(!lim)return f; 56         } 57     } 58     d[u]=0; 59     return f; 60 } 61 int Dinic(){ 62     int res=0; 63     while(BFS())res+=DFS(S,INF); 64     return res; 65 } 66 struct bridge{ 67     int a,b,c,d; 68 }br[mxn]; 69 int deg[mxn],cnt=0; 70 bool Build(int lim){ 71     memset(hd,0,sizeof hd);mct=1; 72     memset(deg,0,sizeof deg);cnt=0; 73     S=0;T=n+1; 74     for(int i=1;i<=m;i++){ 75         if(br[i].c<=lim)deg[br[i].a]--,deg[br[i].b]++; 76         if(br[i].d<=lim)insert(br[i].b,br[i].a,1); 77     } 78     for(int i=1;i<=n;i++){ 79         if(deg[i]&1)return 0; 80         if(deg[i]>0)insert(S,i,deg[i]/2),cnt+=deg[i]/2; 81         else insert(i,T,-deg[i]/2); 82     } 83     return 1; 84 } 85 int mn,mx; 86 void solve(){ 87     int ans=-1; 88     while(mn<=mx){ 89         int mid=(mn+mx)>>1; 90         if(Build(mid) && (cnt==Dinic())){ 91             ans=mid; 92             mx=mid-1; 93         } 94         else mn=mid+1; 95     } 96     if(ans==-1)puts("NIE"); 97     else printf("%d\n",ans); 98     return; 99 }100 int main(){101     int i,j;102     n=read();m=read();103     mn=INF;mx=0;104     for(i=1;i<=m;i++){105         br[i].a=read();br[i].b=read();br[i].c=read();br[i].d=read();106         if(br[i].c>br[i].d){107             swap(br[i].c,br[i].d);108             swap(br[i].a,br[i].b);109         }110         mn=min(mn,br[i].c);111         mx=max(mx,br[i].d);112     }113     solve();114     return 0;115 }