ACM模板库

ACM模板库


有向图匹配

<pre><code class="language-cpp">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;set&gt; #include &lt;algorithm&gt; using namespace std; typedef long long ll; typedef pair&lt;ll, ll&gt; P; const int maxn = 105; int n, m, k; vector&lt;set&lt;int&gt;&gt; mp(maxn); int vis[maxn], pre[maxn]; int c = 0; bool found(int u, int t){ vis[u] = t; for(set&lt;int&gt;::iterator i = mp[u].begin(); i != mp[u].end(); i++){ int v = *i; if(vis[v] == t) continue; vis[v] = t; if(pre[v] == 0 || found(pre[v], t)){ pre[v] = u; return true; } } return false; } //处理有向图的匹配,只一个点只能指向另一个点的匹配 int main(){ scanf("%d%d%d", &amp;n, &amp;m, &amp;k); for(int i = 1; i &lt;= m; i++){ int u, v; scanf("%d%d", &amp;u, &amp;v); mp[u].insert(v+n); //有向图要分成 } for(int i = 1; i &lt;= k; i++){ scanf("%lld%lld", &amp;query[i].first, &amp;query[i].second); } for(int i = 1; i &lt;= n; i++){ //这里是重点 if(found(i, i)) c++; } }</code></pre>

页面列表

ITEM_HTML