<h1>题目描述</h1>
给定一张无向图,求让这张无向图不连通应删去的点的最小个数。
<h1>解题报告</h1>
首先发现这很像割的定义,只不过由边转化为了点。
那我们不妨拆点来对边进行限制:其中对于每个点 $v$ 拆成 $v$ 和 $v'$ ,然后我们在这两个点之间连一条容量为 $1$ 的边,然后原图边容量为 $INF$ ,用最大流最小割定理求解即可。
但是我们发现题目里没有给出源点和汇点,直接的想法是枚举,但是我们其实可以固定一个源点,只枚举汇点就可以了,最后对于每一次的最大流都取个最小值就可以了。
<h1>代码</h1>
#include <algorithm> #include <iostream> #include <cstring> //#include <climits> #define INT_MAX 2147483645 #include <cstdio> #include <vector> #include <cstdlib> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define Re register #define LL long long #define U unsigned #define FOR(i,a,b) for(Re int i = a;i <= b;++i) #define ROF(i,a,b) for(Re int i = a;i >= b;--i) #define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c) #define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c) #define CLR(i,a) memset(i,a,sizeof(i)) #define BR printf("--------------------n") #define DEBUG(x) std::cerr << #x << '=' << x << std::endl #define int LL const int MAXN = 1000+5; const int MAXM = 20000+5; struct Node{ struct Edge first,cur; int level,num; }node[MAXN]; struct Edge{ Node s,t; Edge next,rev; int cap,flow; }pool[MAXM<<1],*frog = pool; Edge New(Node s,Node *t,int cap){ Edge *ret = ++frog; *ret = (Edge){s,t,s->first,NULL,cap,0}; return ret; } inline void add(int u,int v,int cap){ // printf("%d %d %dn",u,v,cap); node[u].first = New(&node[u],&node[v],cap); node[v].first = New(&node[v],&node[u],0); node[u].first->rev = node[v].first; node[v].first->rev = node[u].first; } int S,T,N; bool bfs(Node s,Node t){ FOR(i,0,N){ node[i].cur = node[i].first; node[i].level = 0;node[i].num = i; } std::queue<Node *> q;q.push(s); s->level = 1; while(!q.empty()){ Node *v = q.front();q.pop(); for(Edge *e = v->first;e;e = e->next){ if(e->flow < e->cap && !e->t->level){ e->t->level = v->level + 1; if(e->t == t) return true; q.push(e->t); } } } return false; } int dfs(Node v,Node t,int limit=INT_MAX){ if(v == t) return limit; int flow; for(Edge *&e = v->cur;e;e = e->next){ if(e->flow < e->cap && e->t->level == v->level + 1){ if((flow = dfs(e->t,t,std::min(limit,e->cap-e->flow)))){ e->flow += flow; e->rev->flow -= flow; return flow; } } } return 0; } int dinic(){ int flow,ans=0; for(Edge *e = pool;e != frog+1;e++) e->flow = 0; while(bfs(&node[S],&node[T])){ while((flow = dfs(&node[S],&node[T]))){ ans += flow; } } return ans; } inline void init(){ CLR(node,0);frog = pool; } int n,m; inline void Solve(){ init(); FOR(i,1,m){ int u,v; scanf(" (%lld,%lld)",&u,&v);//u++;v++; add(u+n,v,INT_MAX);add(v+n,u,INT_MAX); } FOR(i,0,n) add(i,i+n,1); S = n;N = (n<<1); int ans = n; FOR(i,1,n-1){ T = i;//DEBUG(ans); ans = std::min(ans,dinic()); } printf("%lldn",ans); } /* 1 2 1 3 2 3 */ signed main(){ while(~scanf("%lld%lld",&n,&m)) Solve(); return 0; } /* 1 4 1 2 5 1 3 6 1 4 2 100000000 5 1 100000000 4 3 100000000 6 1 100000000 5 3 100000000 6 2 100000000 */