P2764 最小路徑覆蓋問題 網路流

2022-09-22 21:31:44 字數 1279 閱讀 6897

戳這裡

模板題題意轉化一下,\(ans=總點數-最大邊數=總點數-最大流\),

我們把每一個點拆成入點和出點兩部分,原點向每一個入點連一條邊,每一個出點向匯點連一條邊,對於原圖上存在的一條邊 \(x\to y\) 由 \(x\) 的入點向 \(y\) 的出點連一條邊,這些邊的流量都是 \(1\) 這樣跑出來的最大流就是原圖上的最大邊數

正確性證明:

按照這樣的方式建圖,每一個點至多和一個點匹配上,而每一個點和另一個點匹配上的時候最大流會增加 \(1\) 這樣最大流就等價於匹配的點對數 \(=\) 圖上最大邊數

另外這個題還很噁心的要輸出方案,看題解後發現,可以通過列舉邊,將流量為 \(0\) 的正邊,\(to\) 併到 \(frm\) 的並查集裡,這樣每一個並查集的代表元就是路徑的一個起點

#includeusing namespace std;

namespace zzc

while(isdigit(ch))

return x*f;

}const int maxn = 305;

const int maxm = 2e4+5;

const int inf = 0x3f3f3f3f;

int head[maxn],dep[maxn],fa[maxn];

int n,m,ans,cnt=1,st,ed;

queueq;

struct edge

e[maxm];

void add_edge(int u,int v,int w)

void add(int u,int v,int w)

int find(int x)

bool bfs()}}

return dep[ed]!=-1;

}int dfs(int u,int f)

}if(!used) dep[u]=-1;

return used;

}void dinic()

}void solve(int u)

} }void work()

for(int i=1;i<=n;i++) fa[i]=i,add(st,i,1),add(i+n,ed,1);

dinic();

for(int i=2;i<=cnt;i++) if(e[i].frm>=1&&e[i].frm<=n&&e[i].to>n&&e[i].tofor(int i=1;i<=n;i++) if(find(i)==i)

printf("%d\n",ans);

}}int main()

P2764 最小路徑覆蓋問題

這個題是一種題型,其實也就是拆一下點。 我們首先將原圖用n條路徑覆蓋,每條邊只經過每個節點。 現在儘量合併更多的路徑 即將兩個路徑通過一條邊...

P2764 最小路徑覆蓋問題

典型的有向無環圖求最小路徑點覆蓋 要求我們選出若干個簡單路徑 將所有的的點覆蓋 且路徑之間不能相交 求最少的路徑條數 我們考慮一個路徑覆蓋 每個點由於都被覆蓋 所以他的入度,出度必然有一個為1 且最大為1 我們之後考慮將每個點拆點 分成入度與出度兩部分 分到兩側 當有一條邊 x y 時 我們將x的出...

洛谷 P2764 最小路徑覆蓋問題(最大流)

題目連結 首先有 n 條路徑,每條路徑就是一個點,然後儘量合併,答案就是點數 合併數。 套路拆點,源連入,出連匯,原有的邊入出連。 最大流就...