nyoj-895 How many ways [그림에서 dp+ 토폴로지]

How many ways?

시간 제한:
1000ms | 메모리 제한:
65535 KB
난이도:
4
묘사
n개의 점 m변의 유방향 무환도를 주고 점 1부터 점 n까지 모두 몇 개의 경로가 있느냐고 묻는다.(결과 10007 모델링)
입력
다중 테스트 데이터.
첫 번째 줄의 두 개수, n과 m(2<=n<=100,2<=m<=10000).
출력
각 그룹의 테스트 데이터 출력은 점 1에서 점 n까지의 방안 수가 10007에서 모형을 추출한 후의 값을 나타낸다.
우선, 내가 이 문제를 분석한 것은 그림의 dp이다.
dp[i][j]로 i점->j점의 최대 경로를 표시합니다
dp[0][j]에서 j점 전체의 최대 경로 수를 기록합니다
g[i][j]는 i점에서 j점까지의 변수
상태 전환 방정식은 다음과 같습니다.
dp[u][v]=Max(dp[0][u]*g[u][v]);
dp[0][v]=∑(Max(dp[u][v]));u는 v에 연결할 수 있는 모든 점입니다
전체적인 의미는 한 점의 최대 경로수는sumv=∑(sumu*count e)이다.v의 최대 경로 수 = 모든 (v의 최대 경로 수 * v에서 u의 변수) 의 합
다음은 모든 변을 열거하고 dp값을 업데이트하는 것입니다.하나의 점의 dp값이 바뀌면 연결된 점과 그 이후의 dp값은 모두 변할 수 있다.그래서 더 이상 업데이트가 없을 때까지 모든 변이 dp값을 업데이트합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max_V 110
long long int dp[Max_V][Max_V];
long long int g[Max_V][Max_V];
int n,m;
void init()
{
	memset(dp,0,sizeof(dp));
	memset(g,0,sizeof(g));	
}
int main()
{
	int i;
	while(~scanf("%d%d",&n,&m))
	{
		init();
		int u,v;
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&u,&v);
			g[u][v]++;
		}
		dp[0][1]=1;// 1   
		bool flag=true;
		while(flag)
		{
			flag=false;
			//     
			for(u=1;u<=n;u++)
				for(v=1;v<=n;v++)
				{
					if(dp[u][v]<g[u][v]*dp[0][u])
					{
						flag=true;
						//dp[0][v]       ，
						//    dp[u][v]       
						//       dp[u][v]
						dp[0][v]-=dp[u][v];
						dp[u][v]=g[u][v]*dp[0][u];
						dp[0][v]+=dp[u][v];
					}
				}
		}
		printf("%lld
",dp[0][n]%10007);
	}
	return 0;
}

하지만 문제가 생겼다.데이터 범위가 매우 넓어서 롱 롱 int를 훨씬 초과한다.모형을 구한 후에 크기를 비교하는 것은 무효이기 때문이다.그럼 이 문제를 어떻게 해결할까요?
키워드:유방향 루프 없음
Lenovo: DAG(토폴로지 정렬)
AOV 네트워크로 토폴로지 서열을 구성하는 토폴로지 정렬 알고리즘은 입도 0의 정점이 존재하지 않을 때까지 다음과 같은 두 단계를 반복한다.
반복 실행 (1) 입도 0의 정점을 선택한다.(2) 네트에서 이 교점과 모든 아웃라인을 삭제합니다.
이렇게 하면 출입도가 0인 점을 끊임없이 열거한다.
상부의 사고방식을 이어받다.한 점의 입도가 0이라는 것은 이 점이 다시는 다른 점에 의해 업데이트되지 않을 것이라는 것을 설명하는 것입니까?이 점이 끝까지 업데이트되었다는 거 아니에요?
그러면 dp[0][u]는 더 이상 바뀌지 않을 것이다.dp[u][v]도 이에 따라 고정된다.이렇게 하면 문제는 단순한 추이식이 되고 dp[]수조는 2차원에서 1차원으로 최적화될 수 있다. dp[v]+=dp[u]*g[u][v];dp[u] 고정(u의 입도는 0이기 때문에 dp[u]는 다시 변경되지 않기 때문에 dp[u]는 현재 최대 경로수), g[u][v]는 고정됩니다.
더 이상 크기를 판단할 필요가 없다.추출 연산을 이용할 수 있다.
따라서 이 점에서 다른 점을 업데이트한 후에 이 점과 그 아웃라인을 삭제할 수 있고 출입도가 0인 점을 만들 수 있다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Max_V 110
#define mod 10007
int n,m;
int indeg[Max_V];
int g[Max_V][Max_V];
int dp[Max_V];
bool vis[Max_V];
void init()
{
	memset(indeg,0,sizeof(indeg));
	memset(g,0,sizeof(g));
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
}
int main()
{
	int i;
	while(~scanf("%d%d",&n,&m))
	{
		init();
		int u,v;
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&u,&v);
			g[u][v]++;
			indeg[v]++;
		}
		dp[1]=1;
		while(true)
		{
			for(u=1;u<=n;u++)//      0   
				if(!indeg[u]&&!vis[u])
					break;
			if(u>=n)
				break;
			vis[u]=1;//          
			for(v=1;v<=n;v++)
				if(g[u][v])
				{
					dp[v]+=dp[u]*g[u][v];//（a+b）%m=(a%m+b%m)%m
					dp[v]%=mod;
					indeg[v]-=g[u][v];//             
				}
		}
		printf("%d
",dp[n]);
	}
	return 0;
}