cjb-poi2010bridges
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <cassert>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
struct node
{
int x,y,w1,w2;
void read(){ scanf("%d%d%d%d",&x,&y,&w1,&w2); if (w1>w2)swap(x,y),swap(w1,w2); }
}a[2100];
int n,m;
int ru[1100],chu[1100],cnt;
#define N 1100
#define M 10100
struct EDGE { int adj, w, next; } edge[M];
int top, gh[N], nrl[N],S,T;
void addedge(int x, int y, int w) {
edge[++top].adj = y;
edge[top].w = w;
edge[top].next = gh[x];
gh[x] = top;
edge[++top].adj = x;
edge[top].w = 0;
edge[top].next = gh[y];
gh[y] = top;
}
int dist[N], q[N];
int bfs() {
memset(dist, 0, sizeof(dist));
q[1] = S; int head = 0, tail = 1; dist[S] = 1;
while (head != tail) {
int x = q[++head];
for (int p=gh[x]; p; p=edge[p].next)
if (edge[p].w && !dist[edge[p].adj]) {
dist[edge[p].adj] = dist[x] + 1;
q[++tail] = edge[p].adj;
}
}
return dist[T];
}
int dinic(int x, int delta) {
if (x==T) return delta;
for (int& p=nrl[x]; p && delta; p=edge[p].next)
if (edge[p].w && dist[x]+1 == dist[edge[p].adj]) {
int dd = dinic(edge[p].adj, min(delta, edge[p].w));
if (!dd) continue;
edge[p].w -= dd;
edge[p^1].w += dd;
return dd;
}
return 0;
}
int work() {
int ans = 0;
while (bfs()) {
memcpy(nrl, gh, sizeof(gh));
int t; while (t = dinic(S, 2147483647)) ans += t;
}
return ans;
}
bool check(int limit)
{
for(int i=0;i<=n+1;i++)gh[i]=0; top=1;
S=0; T=n+1;
rep(i,m)
{
if (a[i].w1>limit)return 0;
if (a[i].w2<=limit)addedge(a[i].x,a[i].y,1);
}
rep(i,n)
{
if (chu[i]>ru[i])addedge(S,i,(chu[i]-ru[i])/2);
else if (chu[i]<ru[i])addedge(i,T,(ru[i]-chu[i])/2);
}
if (work()==cnt/2)return 1;
return 0;
}
namespace DirectedGraph{
int n,m,i,x,y,d[N],g[N],v[M],vis[M],nxt[M],ed;
int ans[M],cnt;
void add(int x,int y){
//cout<<x<<" "<<y<<endl;
d[x]++;d[y]--;
v[++ed]=y;nxt[ed]=g[x];g[x]=ed;
}
void dfs(int x){
for(int&i=g[x];i;){
if(vis[i]){i=nxt[i];continue;}
vis[i]=1;
int j=i;
dfs(v[i]);
ans[++cnt]=j;
}
}
void solve(){
dfs(1);
for(i=m;i;i--)printf("%d%c",ans[i],i==1?'\n':' ');
}
}
void print(int limit)
{
check(limit);
DirectedGraph::n=n;
DirectedGraph::m=m;
top=1;
rep(i,m)
{
if (a[i].w2<=limit)
{
++top;
if (edge[top++].w==0)DirectedGraph::add(a[i].y,a[i].x);
else DirectedGraph::add(a[i].x,a[i].y);
}else DirectedGraph::add(a[i].x,a[i].y);
}
cout<<limit<<endl;
DirectedGraph::solve();
}
int main()
{
cin>>n>>m;
rep(i,m)a[i].read();
int l=1; int r=1000;
rep(i,n)ru[i]=chu[i]=0;
rep(i,m)chu[a[i].x]++,ru[a[i].y]++;
cnt=0;
rep(i,n)
{
if ((chu[i]-ru[i])%2!=0){ puts("NIE"); return 0; }
cnt+=abs(chu[i]-ru[i])/2;
}
while (l<r)
{
int mid=(l+r)/2;
if (check(mid))r=mid; else l=mid+1;
}
print(l);
}
}}}#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <cassert>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
struct node
{
int x,y,w1,w2;
void read(){ scanf("%d%d%d%d",&x,&y,&w1,&w2); if (w1>w2)swap(x,y),swap(w1,w2); }
}a[2100];
int n,m;
int ru[1100],chu[1100],cnt;
#define N 1100
#define M 10100
struct EDGE { int adj, w, next; } edge[M];
int top, gh[N], nrl[N],S,T;
void addedge(int x, int y, int w) {
edge[++top].adj = y;
edge[top].w = w;
edge[top].next = gh[x];
gh[x] = top;
edge[++top].adj = x;
edge[top].w = 0;
edge[top].next = gh[y];
gh[y] = top;
}
int dist[N], q[N];
int bfs() {
memset(dist, 0, sizeof(dist));
q[1] = S; int head = 0, tail = 1; dist[S] = 1;
while (head != tail) {
int x = q[++head];
for (int p=gh[x]; p; p=edge[p].next)
if (edge[p].w && !dist[edge[p].adj]) {
dist[edge[p].adj] = dist[x] + 1;
q[++tail] = edge[p].adj;
}
}
return dist[T];
}
int dinic(int x, int delta) {
if (x==T) return delta;
for (int& p=nrl[x]; p && delta; p=edge[p].next)
if (edge[p].w && dist[x]+1 == dist[edge[p].adj]) {
int dd = dinic(edge[p].adj, min(delta, edge[p].w));
if (!dd) continue;
edge[p].w -= dd;
edge[p^1].w += dd;
return dd;
}
return 0;
}
int work() {
int ans = 0;
while (bfs()) {
memcpy(nrl, gh, sizeof(gh));
int t; while (t = dinic(S, 2147483647)) ans += t;
}
return ans;
}
bool check(int limit)
{
for(int i=0;i<=n+1;i++)gh[i]=0; top=1;
S=0; T=n+1;
rep(i,m)
{
if (a[i].w1>limit)return 0;
if (a[i].w2<=limit)addedge(a[i].x,a[i].y,1);
}
rep(i,n)
{
if (chu[i]>ru[i])addedge(S,i,(chu[i]-ru[i])/2);
else if (chu[i]<ru[i])addedge(i,T,(ru[i]-chu[i])/2);
}
if (work()==cnt/2)return 1;
return 0;
}
namespace DirectedGraph{
int n,m,i,x,y,d[N],g[N],v[M],vis[M],nxt[M],ed;
int ans[M],cnt;
void add(int x,int y){
//cout<<x<<" "<<y<<endl;
d[x]++;d[y]--;
v[++ed]=y;nxt[ed]=g[x];g[x]=ed;
}
void dfs(int x){
for(int&i=g[x];i;){
if(vis[i]){i=nxt[i];continue;}
vis[i]=1;
int j=i;
dfs(v[i]);
ans[++cnt]=j;
}
}
void solve(){
dfs(1);
for(i=m;i;i--)printf("%d%c",ans[i],i==1?'\n':' ');
}
}
void print(int limit)
{
check(limit);
DirectedGraph::n=n;
DirectedGraph::m=m;
top=1;
rep(i,m)
{
if (a[i].w2<=limit)
{
++top;
if (edge[top++].w==0)DirectedGraph::add(a[i].y,a[i].x);
else DirectedGraph::add(a[i].x,a[i].y);
}else DirectedGraph::add(a[i].x,a[i].y);
}
cout<<limit<<endl;
DirectedGraph::solve();
}
int main()
{
cin>>n>>m;
rep(i,m)a[i].read();
int l=1; int r=1000;
rep(i,n)ru[i]=chu[i]=0;
rep(i,m)chu[a[i].x]++,ru[a[i].y]++;
cnt=0;
rep(i,n)
{
if ((chu[i]-ru[i])%2!=0){ puts("NIE"); return 0; }
cnt+=abs(chu[i]-ru[i])/2;
}
while (l<r)
{
int mid=(l+r)/2;
if (check(mid))r=mid; else l=mid+1;
}
print(l);
}