Codeforces ラウンド #277.5 (ディビジョン 2) D??Being_html/css_WEB-ITnose に関する耐え難い論争-htmlチュートリアル-php.cn

Codeforces ラウンド #277.5 (ディビジョン 2) D??Being_html/css_WEB-ITnose に関する耐え難い論争

WBOY

リリース： 2016-06-24 11:53:48

オリジナル

1266 人が閲覧しました

D. 存在についての耐え難い論争

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

トマシュはベルランドの通りを歩いている間、何度もさまよい、道に迷ってしまいます。それは驚くことではありません。彼の故郷では、どの交差点でも、一方の交差点からもう一方の交差点まで歩く方法が 1 つだけあります。ベルラントの首都はまったく異なります!

Tomash は、単純なあいまいさの場合でも混乱することに気づきました。したがって、彼が 4 つの異なる交差点 a、b、c、d のグループを見たとき、a から c への 2 つのパスが存在することになります。 1 つは b まで、もう 1 つは d まで、彼はそのグループを「ひどいひし形」と呼んでいます。ペア (a,?b)、(b,?c)、(a,?d)、(d,?c) は道路によって直接接続されている必要があることに注意してください。概略的には、ひどいひし形が下の図に示されています:

どの交差点の間に他の道路があるとしても、Tomash にとってそのひし形はそれ以上魅力的ではありません。そのため、4 つの交差点は彼にとって「ひどいひし形」のままです。

それを考慮すると、ベルラントの首都には n 個の交差点と m 個の道路があり、すべての道路は一方向であり、事前にわかっています。市内にある「いまいましいひし形」の数を見つけてください。

ひし形を比較するとき、交差点 b と d の順序は一致しません。 matter.

入力

入力の最初の行には、整数 n、m のペアが含まれています (1?≤?n?≤?3000,?0?≤?m?≤?30000) ?それぞれ交差点と道路の数。次の m 行には、1 行に 1 つずつ道路がリストされます。各道路は、一対の整数ａｉ、?ｂｉ（１?≤?ａｉ、?ｂｉ?≤?ｎ；ａｉ?≠?ｂｉ）によって与えられる。出発する交差点の番号と、そこに至る交差点の番号。 2 つの交差点の間には、2 つの方向のそれぞれに最大で 1 本の道路があります。

どの交差点から他の交差点にも行けるという保証はありません。

出力

必要な数の「くそー」を出力します。 rhombi".

サンプルテスト

入力

5 41 22 31 44 3

ログイン後にコピー

出力

入力

4 121 21 31 42 12 32 43 13 23 44 14 24 3

ログイン後にコピー

出力

ログイン後にコピー

水题、只要计算出每点走二步後达第三点の全走法、その後C(2, n)

#include <map>#include <set>#include <list>#include <queue>#include <stack>#include <vector>#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 3010;const int M = 30010;struct node{	int next;	int to;}edge[M];int head[N];int tot;int num[N][N];void addedge(int from, int to){	edge[tot].to = to;	edge[tot].next = head[from];	head[from] = tot++;}int main(){	int n, m;	while (~scanf("%d%d", &n, &m))	{		int u, v, w;		memset (head, -1, sizeof(head));		memset (num, 0, sizeof(num));		tot = 0;		for (int i = 1; i <= m; ++i)		{			scanf("%d%d", &u, &v);			addedge(u, v);		}		for (u = 1; u <= n; ++u)		{			for (int i = head[u]; ~i; i = edge[i].next)			{				v = edge[i].to;				for (int j = head[v]; ~j; j = edge[j].next)				{					w = edge[j].to;					num[u][w]++;				}			}		}		__int64 ans = 0;		for (int i = 1; i <= n; ++i)		{			for (int j = 1; j <= n; ++j)			{				if (i == j)				{					continue;				}				ans += (__int64)(num[i][j] - 1) * num[i][j] / 2;			}		}		printf("%I64d\n", ans);	}	return 0;}

ログイン後にコピー