题目描述
In the country of Via, the cities are connected by roads that can be used in both directions.
However, this has been the cause of many accidents since the lanes are not separated: The drivers frequently look at their smartphones while driving, causing them to collide with the oncoming traffic. To alleviate the problem, the politicians of Via came up with the magnificent idea to have one-way roads only, i.e., the existing roads are altered such that each can be only used in one of two possible directions. They call this “one-way-ification”.
The mayors do not want too many one-way roads to lead to their cities because this can cause traffic jam within the city: they demand that the smallest integer d be found such that there is a ‘one-way-ification’ in which for every city, the number of one-way roads leading to it is at most d.
输入
The input consists of:
• one line with an integer n (1 ≤ n ≤ 500), where n is the number of cities labeled from 1 to n;
• one line with an integer m (0 ≤ m ≤ 2.5 · 103 ), where m is the number of (bi-directional) roads;
• m lines describing the roads. Each road is described by:
– one line with two integers a and b (1 ≤ a, b ≤ n, a≠b) indicating a road between cities a and b.
There is at most one road between two cities.
输出
Output the minimum number d.
样例输入
2
1
1 2
样例输出
1
题意： 一个国家有N个城市，m个双向道路，现在要把所有双向道路改成单项道路，问改成单向道路之后所有城市中入度最大的至少是多少。
最大流建图：
每条边转换成一个节点，代表一条边的该节点有两条边指向该边连接 的两城市，容量为1。所有城市连向超级汇点，容量为x，表示二分出来的入度，通过限制入度的方式限制最大流。超级源点连向每一条代表边的节点，容量为1。
跑出来的最大流即在该最大入度下能正常走到的边数。
建图大概形态如下：
这样一开始每条边的容量1，保证了每条边只能被走一次，然后连到城市的容量可能有多条路径，这样使得流量增加，通过了一个城市的入度即使如此。接着城市连向超级汇点会被度数x限制，因此当度数较低时，一些被迫，不得不承接那么多道路入度的城市，将会因为被限制了度数而不能跑出满流，满流的形态即m条道路都能走过，就表示是所有道路都被改成了单行道，当不满流时表示二分出来的最大度数太少了，连基本的满流都做不到，需要提高二分出来的度数。
而当能跑出满流时，就面临了一些道路的走向选择，是指向两个城市中的哪一个，这样的抉择将决定着城市的最大入度，最小化最大入度即从这里入手。我们通过在满流的条件下不断压缩最大度数，来实现单向边的方向选择，尽量对承受太多入度的城市分摊掉度数。
#include<bits/stdc++.h>
#define LL long long
#define M(a,b) memset(a,b,sizeof a)
#define pb(x) push_back(x)
using namespace std;
const int maxn=5080;
const int inf=0x3f3f3f3f;
struct edge
{
int to,val,nxt;
edge(){}
edge(int a,int b,int c)
{
to=a,val=b,nxt=c;
}
}mp[maxn*10];
int head[maxn],cnt;
int n,m;
struct node
{
int from,to;
}a[maxn];
void addedge(int from,int to,int val)
{
mp[cnt]=edge(to,val,head[from]);
head[from]=cnt++;
mp[cnt]=edge(from,0,head[to]);
head[to]=cnt++;
}
int dep[maxn];
bool bfs(int st,int ed)
{
M(dep,-1);
queue<int>q;
while(!q.empty())q.pop();
dep[st]=0;
q.push(st);
while(!q.empty())
{
int tmp=q.front();
q.pop();
if(tmp==ed) return true;
for(int i=head[tmp]; i!=-1; i=mp[i].nxt)
{
int &to=mp[i].to,flow=mp[i].val;
if(dep[to]==-1&&flow)
{
dep[to]=dep[tmp]+1;
q.push(to);
if(to==ed)return true;
}
}
}
return false;
}
int cur[maxn];
int dfs(int s,int t,int flow)
{
if(s==t||flow==0)return flow;
int pre=0;
for(int &i=cur[s]; i!=-1; i=mp[i].nxt)
{
int &to=mp[i].to,val=mp[i].val;
if(dep[s]+1==dep[to]&&val)
{
int tmp=min(flow-pre,val);
int sub=dfs(to,t,tmp);
mp[i].val-=sub;
mp[i^1].val+=sub;
pre+=sub;
if(pre==flow)return pre;
}
}
return pre;
}
int dinic(int st,int ed)
{
int ans=0;
while(bfs(st,ed))
{
for(int i=1;i<=n+m+2;i++)cur[i]=head[i];
ans+=dfs(st,ed,inf);
}
return ans;
}
bool judge(int x)
{
M(head,-1);
cnt=0;
int st=n+m+1;
int ed=st+1;
for(int i=1;i<=m;i++)
{
addedge(st,i,1);
addedge(i,m+a[i].from,1);
addedge(i,m+a[i].to,1);
}
for(int i=1;i<=n;i++) addedge(m+i,ed,x);
return dinic(st,ed)==m;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&a[i].from,&a[i].to);
int l=0,r=n,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(judge(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d
",ans);
}