题目:
题解:
我不想写这道题的题解
Sky_miner是我的号hzoi_admin是我提交次数不够了借用的号.
求不D
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef int ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 80048;
const int maxm = 100005;
const int maxnode = (maxn+maxm)<<1;
struct Edge{
int to,next;
long double cap;
}G[maxnode];
int head[maxnode],cnt=1;
void add(int u,int v,long double c){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
G[cnt].cap = c;
}
inline void insert(int u,int v,long double c){
add(u,v,c);add(v,u,0);
}
inline void clear(){
memset(head,-1,sizeof head);
cnt = 1;
}
#define v G[i].to
int dis[maxnode];
int S,T;
inline bool bfs(){
memset(dis,-1,sizeof dis);
queue<int>q;q.push(S);
dis[S] = 0;
while(!q.empty()){
int u = q.front();q.pop();
for(int i = head[u];i != -1;i=G[i].next){
if(dis[v] == -1 && G[i].cap > 1e-8){
dis[v] = dis[u] + 1;
q.push(v);
}
}
}return dis[T] != -1;
}
long double dfs(int u,long double f){
if(u == T || fabs(f) < 1e-8) return f;
long double ret = 0;
for(int i = head[u];i != -1;i=G[i].next){
if(dis[v] == dis[u] + 1 && G[i].cap > 1e-8 ){
long double x = dfs(v,min(G[i].cap,f));
ret += x;f -= x;
G[i].cap -= x;
G[i^1].cap += x;
if(fabs(f) < 1e-8) break;
}
}return ret;
}
#undef v
inline long double dinic(){
long double ret = 0;
while(bfs()) ret += dfs(S,1e9);
return ret;
}
struct Node{
int u,v;
}e[maxm];
int n,m;
bool check(double ans){
memset(head,-1,sizeof(head));cnt=1;
double sum=m;S=0;T=n+m+1;
for(int i=1;i<=n;++i){
insert(S,i,ans);
}
for(int i=1;i<=m;++i){
insert(n+i,T,1);
insert(e[i].u,n+i,1e9);
insert(e[i].v,n+i,1e9);
}
return sum>dinic();
}
int dfn[maxn];
int ans;
void DFS(int x){
if(1<=x&&x<=n)ans--;
dfn[x]=1;
for(int pt=head[x];pt!=-1;pt=G[pt].next){
if(G[pt].cap>1e-3&&!dfn[G[pt].to])DFS(G[pt].to);
}
}
int main(){
read(n);read(m);
if(m == 0) return puts("1");
for(int i=1;i<=m;++i){
read(e[i].u);read(e[i].v);
}
long double l = .0,r = 1e4;
while(l + 1e-5 < r){
long double mid = (l+r)/2.0;
if(check(mid)) l = mid;
else r = mid;
}ans = n;
DFS(S);
printf("%d\n",max(ans,1));
getchar();getchar();
return 0;
}