不相交路径

Time Limit:10000MS  Memory Limit:65536K
Total Submit:40 Accepted:14
Case Time Limit:1000MS

Description

给出一个N(n<=150)个结点的有向无环简单图。给出4个不同的点a,b,c,d，定义不相交路径为两条路径，两条路径的起点分别为a 和c，对应的两条路径的终点为b和d，要求满足这两条路径不相交，即两条路径上没有公共的点。
现在要求不相交路径的方案数。

Input

第一行为N，M。表示这个有向无环图有N个节点，M条边。
接下来M行，每行两个整数x,y。表示x至y有一条有向边。
接下来一行四个数a,b,c,d，意义如题中所述。

Output

输出为一行，即答案（方案数）。

Sample Input

5 6
1 5
1 3
2 5
2 4
5 3
5 4
1 3 2 4

Sample Output

3

Source
我看到这个题目之后。。第一感觉就是需要高精。。
然后感觉正难则反嘛。。所以可以用补集转化。。
首先拓扑排序一下。。
然后设G[s][t]为s到t的路径条数。。
随便Dp一下就出来了。。
然后设F[t]为s1->t,s2->t之前不相交的路径对数。。
显然枚举一下在前面相交的，减掉即可。。
F[t]=G[s1][t]*G[s2][t]-Sum{F[k]*G[k][t]^2}..
然后就差不多OK了。。
Ans=G[s1][t1]*G[s2][t2]-Sum{F[k]*G[k][t1]*G[k][t2]}。。
就OK了。。