大意: 給定$n$結點無向圖, 共n條邊, 有重邊無自環, 求有多少點對(u,v), 滿足經過u和v的邊數>=p

?

?

?

?

可以用雙指針先求出所有$deg_u+deg_v \ge p$的點對, 但這樣會多算一些有公共邊的

再枚舉邊, 減去?$deg_u+deg_v-cnt(u,v) < p$的即可

其中$deg$為點的度數, $cnt(u,v)$為$u$與$v$之間的邊數

#include <iostream> #include <algorithm> #include <cstdio> #include <map> #define REP(i,a,n) for(int i=a;i<=n;++i)using namespace std; typedef long long ll; typedef pair<int,int> pii;const int N = 2e6+10; map<pair<int,int>,int> g; int deg[N], n, p;int main() {scanf("%d%d", &n, &p);REP(i,1,n) {int u, v;scanf("%d%d", &u, &v);if (u>v) swap(u,v);++g[pii(u,v)],++deg[u],++deg[v];}ll ans = 0;for (auto it:g) {int x=it.first.first,y=it.first.second;if (deg[x]+deg[y]>=p&&deg[x]+deg[y]-it.second<p) --ans;}sort(deg+1,deg+1+n);int now = n;REP(i,1,n) {while (now>i&&deg[now]+deg[i]>=p) --now;ans += n-max(i,now);}printf("%lld\n",ans); }

?

轉載于:https://www.cnblogs.com/uid001/p/10428080.html

總結

以上是生活随笔為你收集整理的Bug in Code CodeForces - 420C (计数,图论)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。