題目鏈接：點擊查看

題目大意：給出左右兩個子集分別，再給出k條邊，問能否找出四個點，讓其連成一條路徑

題目分析：一開始看到這個題肯定是個二分圖，又因為有邊，我就往度數上面想，一看四個點，就在想能不能枚舉每一條邊，因為邊的兩頭就是兩個點了，然后這兩個點的度數就決定了以當前邊為中間邊的所有情況了，于是這樣寫了一發。。感覺沒什么問題，就是在中間過程會爆int，記得開longlong就好了，然后最后結果記得乘2，因為跑出樣例來發現總是是二分之一的關系，后來想了一下發現是因為每個羊都可以作為起點，然后算出來的那些邊反著也可以跑，所以最后答案要乘2

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int boy[N],girl[N];//記錄度數 int a[N],b[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){memset(girl,0,sizeof(girl));memset(boy,0,sizeof(boy));int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=k;i++){scanf("%d%d",a+i,b+i);boy[a[i]]++;girl[b[i]]++;}LL ans=0;for(int i=1;i<=k;i++)ans+=(boy[a[i]]-1)*(girl[b[i]]-1);printf("%lld\n",ans*2);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 6016 Count the Sheep(二分图+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

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