题目
二分答案然后混合图欧拉回路。
注意在判断是否有解时要记得判断连通性。
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=1007,M=50007,inf=1e9;
int read(){int x;scanf("%d",&x);return x;}
struct edge{int u,v,a,b;}e[M];
int n,m,s,t,tot,deg[N],vis[M],head[N],ver[M],next[M];
std::stack<int>ans;
namespace netflow
{
int head[N],ver[M],edge[M],next[M],tot=1,cur[N],dep[N];std::queue<int>q;
void add(int u,int v,int w){ver[++tot]=v,next[tot]=head[u],edge[tot]=w,head[u]=tot,ver[++tot]=u,next[tot]=head[v],edge[tot]=0,head[v]=tot;}
void clear(){memset(head+1,0,t<<2),tot=1;}
int bfs()
{
memset(dep+1,0x3f,t<<2),memcpy(cur+1,head+1,t<<2),dep[s]=0,q.push(s);
for(int i,u,v;!q.empty();) for(u=q.front(),q.pop(),i=head[u];i;i=next[i]) if(dep[v=ver[i]]>inf&&edge[i]) dep[v]=dep[u]+1,q.push(v);
return dep[t]<inf;
}
int dfs(int u,int lim)
{
if(!lim||u==t) return lim;
int v,f,flow=0;
for(int&i=cur[u];i;i=next[i]) if(dep[v=ver[i]]==dep[u]+1&&(f=dfs(v,std::min(lim,edge[i])))) flow+=f,lim-=f,edge[i]-=f,edge[i^1]+=f;
return flow;
}
int dinic()
{
int maxflow=0;
while(bfs()) maxflow+=dfs(s,inf);
return maxflow;
}
}
void add(int u,int v){ver[++tot]=v,next[tot]=head[u],head[u]=tot;}
void clear(){memset(deg+1,0,n<<2),memset(head+1,0,n<<2),memset(vis+1,0,n<<2),tot=0;}
void Dfs(int u){vis[u]=1;for(int i=head[u];i;i=next[i])if(!vis[ver[i]])Dfs(ver[i]);}
int check(int lim)
{
int sum=0;
netflow::clear(),clear();
for(int i=1;i<=m;++i)
{
int u=e[i].u,v=e[i].v,a=e[i].a,b=e[i].b;
if(std::max(a,b)<=lim) ++deg[u],--deg[v],netflow::add(v,u,1),add(u,v),add(v,u);
else if(a<=lim) ++deg[u],--deg[v],add(u,v);
else if(b<=lim) ++deg[v],--deg[u],add(v,u);
}
Dfs(1);
for(int i=1;i<=n;++i) if(!vis[i]) return 0;
for(int i=1,d;i<=n;++i)
{
if((d=abs(deg[i]))&1) return 0;
if(deg[i]<0) netflow::add(s,i,d/2),sum+=d/2;
if(deg[i]>0) netflow::add(i,t,d/2);
}
return netflow::dinic()==sum;
}
void dfs(int u){for(int i;head[u];) vis[i=head[u]]? head[u]=next[head[u]]:(vis[i]=1,dfs(ver[i]),ans.push(i),0);}
void work(int lim)
{
clear();
for(int i=1,id=2;i<=m;++i)
{
int u=e[i].u,v=e[i].v,a=e[i].a,b=e[i].b;
if(std::max(a,b)<=lim) netflow::edge[id]? add(u,v):add(v,u),id+=2;
else if(a<=lim) add(u,v);
else if(b<=lim) add(v,u);
}
for(dfs(1);!ans.empty();ans.pop()) printf("%d ",ans.top());
}
int main()
{
n=read(),m=read(),s=n+1,t=n+2;int ans=inf;
for(int i=1;i<=m;++i) e[i]={read(),read(),read(),read()};
for(int l=0,r=1000,mid;l<=r;) check(mid=(l+r)>>1)? ans=mid,r=mid-1:l=mid+1;
if(ans==inf) puts("NIE"); else printf("%d
",ans),check(ans),work(ans);
}