题目链接
A 题意分析：n条直线将地图切成多个块，起点终点都在块上，问从起点到终点，最少要走多少步？（有公共边的块认为是相邻的块）
解题思路：猜想：A、B两点间的线段与多少条直线相交，就是我们需要走的步数。即：步数 = 与线段相交的直线条数（直接搜题解的朋友，建议看到这里就自己去实现一方，或者自己去证明下）
#include<bits/stdc++.h> using namespace std; const double eps = 1e-7; int main() { double x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2; int ans = 0; int n; cin>>n; for(int i=0;i<n;i++) { double a,b,c; cin>>a>>b>>c; if((a*x1+b*y1+c)*(a*x2+b*y2+c)<0) ++ans; } cout<<ans<<endl; return 0; }G：首先为一些定义：
假设G =（V，E）是一个包含边u =（u，v）且u≠v的无向图。设f是映射V \ {u，v}中每个顶点到自身的函数，否则，将其映射到一个新的顶点w。e的收缩产生了一个新的图G’=（V’，E’），其中V’=（V \ {u，v}）∪{w}，E’= E \ {e} x∈V，x’= f（x）∈V’入射到边e’∈E’当且仅当相应的边e∈E入射到x中的x。
一个无向图H被称为图G的一个次微分，如果H同构于一个图，可以通过G的一个子图上零个或多个边收缩来获得。
如果任何两个顶点之间存在路径，则连接图。双连接图即使在移除任何一个顶点和所有的边缘之后仍保持连接。
一个简单的图是在任何一对顶点之间没有多于一个边的图，也没有从顶点到它自身的边。
您需要计算有多少个具有n个顶点和m个边的简单双连通图，使得它们不具有长度为5的周期作为次要。如果存在具有在第一图中相邻的标签i和j的顶点而不是在第二图中存在两个图，则认为两个图是不同的。
输入：
第一行包含测试用例T.每个下一行包含两个整数n和m。
输出：
输出T行，一个对应于每个测试用例。对于测试用例，请输出问题中所述的图表数量。输出答案模1000000007。
样本输入： 5 1 0 3 2 3 3 4 4 5 10
采样输出： 1 0 1 3 0
约束条件： 1 <= T <= 2000 1 <= n <= 100 0 <= m <= 10000
可以证明，如果G有一个长度大于等于5的周期，则G有一个长度为5的周期。所以我们希望计算没有长度≥5的周期的双连通图。
现在，我们首先证明任何具有n> = 5顶点的双连通图具有至少为4的长度的周期。考虑没有连接的任何节点u和v。由于u和v之间存在至少两条不相交的路径（每一个长度> = 2），所以我们可以将它们组合起来形成一个长度大于等于4的周期。因此，唯一的可能性是对于所有u，v都有一个边之间。但是在这种情况下，图是一个团，并且具有长度≥4的周期。因此，具有> = 5个顶点的所有双连通分量都具有周期。
现在我们可以使用两个连通图的一个耳朵分解。结果基本上说，我们可以从G中的任何循环开始，并通过向G添加最大路径（耳朵）来逐步形成图形。因此，我们从具有4个节点的循环开始（一个确实存在，就像我们上面看到的那样）。现在分析几个例子，发现增加耳朵到G的唯一方法是在1对角线之间，每个耳朵的长度应该是2，在其他情况下，我们得到一个长度大于等于5的周期。因此，G看起来像这样：有两个节点u和v，它们之间有n-2条长度为2的不相交路径。如果需要，我们可以选择在u和v之间添加直接边缘。因此，G中边的总数是2 （n-2）或2 （n-2）+1。我们可以用ncr（n，2）方法选择u和v。这给了我们以下结果：
如果n = 1，则输出1（如果m = 0），否则输出0 如果n = 2，则输出1（如果m = 1），否则输出0 如果n = 3，则输出1（如果m = 3），否则输出0 如果n = 4，则输出3（如果m = 4）。如果m = 6输出1，否则如果m = 5输出6.否则输出0 对于n> = 5，如果m = 2 （n-2）或m = 2 （n-2）+1，则输出n *（n-1）/ 2。否则输出0。
#include<bits/stdc++.h> using namespace std; const double eps = 1e-7; int main() { int t,n,m; cin>>t; while(t--) { cin>>n>>m; int ans = 0; if(n==1) { if(m==0) { ans = 1; } } else if(n==2) { if(m==1) { ans = 1; } } else if(n==3) { if(m==3) { ans = 1; } } else if(n==4) { if(m==4)ans = 3; if(m==6)ans = 1; if(m==5)ans = 6; } else if(m==2*(n-2)) { ans=n*(n-1)/2; } else if(m==(2*(n-2)+1)) { ans=n*(n-1)/2; } cout<<ans<<endl; } return 0; }It can be shown that G has a cycle of length 5 as a minor iff G has a cycle of length >= 5 in it. So we wish to count biconnected graphs having no cycle of length >= 5.
We start by working out a few special cases for n <= 4. Now, first we show that any biconnected graph having n >= 5 vertices has a cycle of length atleast 4. Consider any nodes u and v which are not connected. Since there are atleast 2 disjoint paths between u and v (each of length >= 2), we can combine them to form a cycle of length >= 4. Hence, the only possibility is that for all u,v there is an edge between then. But in that case, the graph is a clique and has a cycle of length >= 4. Thus, all biconnected components having >= 5 vertices have a cycle.
Now we can use an ear decomposition of two connected graphs. The result basically says that we can start off with any cycle in G, and form the graph progressively by adding maximal paths (ears) to G. So we start off with a cycle having 4 nodes (one surely exists, as we have seen above). Now analysing a few cases reveals that the only way to add ears to G are between 1 diagonal, and each ear should have length exactly 2. In all other cases, we get a cycle of length >= 5. Thus, G looks like this : there are two nodes u and v, with n - 2 disjoint paths of length 2 between them. We can optionally add a direct edge between u and v if needed. Thus, the total number of edges in G are either 2 * (n-2) or 2 * (n-2) + 1. We can choose u and v in ncr(n,2) ways. This gives us the following result :
if n = 1, output 1 if m = 0, else 0 if n = 2, output 1 if m = 1, else 0 if n = 3, output 1 if m = 3, else 0 if n = 4, output 3 if m = 4. If m = 6 output 1, else if m = 5 output 6. else output 0 for n >= 5, output n * (n-1)/2 if m = 2 * (n-2) or m = 2 * (n-2) + 1. else output 0.
