竟然发现自己不会在图中找环，写了近两个小时都没把这个找环的内容处理好。
还是从网上荡下来一个。
从每个点开始做一遍dfs找到最大若有点回到该点则说明有环路，
要么就dfs出一条最长的通路。

 1#include<cstdio>
 2#include<cstring>
 3using namespace std;
 4#define MN 101
 5int map[MN][MN];
 6int flag[MN];
 7int n,root,cost,f;
 8void dfs(int x,int s)
 9{
10     if(f)
11     return ;
12     if(s>=cost)
13     {
14                f=1;
15                return ;
16     }
17     for(int i=1;i<=n;i++)
18     {
19         if(!flag[i]&&map[x][i])
20         {
21            int tmp=map[x][i];
22            map[x][i]=map[i][x]=0;  //选择了该条边在最长路上 
23            flag[i]=1;
24            if(i==root)  //有环路 
25            {
26                   f=1;
27                   return ;
28            }
29            dfs(i,s+tmp);
30            map[x][i]=map[i][x]=tmp;  //不选择这条边在最长路上 
31            flag[i]=0;
32            if(f)
33            return;
34         }
35     }
36}
37int main()
38{
39    int m,i,a,b,d;
40    while(scanf("%d%d%d",&n,&m,&cost)!=EOF)
41    {
42        memset(flag,0,sizeof(flag));
43        memset(map,0,sizeof(map));
44        f=0;
45        for(i=0;i<m;i++)
46        {
47             scanf("%d%d%d",&a,&b,&d);
48             if(!map[a][b])
49             map[a][b]=map[b][a]=d;
50             else
51             f=1;
52        }
53        for(i=1;i<=n&&!f;i++)
54        {
55            memset(flag,0,sizeof(flag));
56            root=i;
57            dfs(i,0);
58        }
59        if(f)
60        puts("YES");
61        else
62        puts("NO");
63    }
64    return 0;
65}

很多问题都可以转化成网络流问题，如运输货物时的物流问题，水流问题，匹配问题等等。网络是一个各条边都有权值和方向的图。

网络流问题，一般情况下我们会把各种网络问题抽象成网络流问题，网络流是满足以下性质的网络：每一条边拥有一个最大的容量c，即该条边可以容纳的最大流量，f是流过该边的实际流量，且总有f<=c。对于图中每个顶点（源点和汇点除外）都有流出的流量等于流入的流量。图中只有一个源点一个汇点，且对于源点来说其流入量为0，对于汇点来说流出量为0，源点的流出量等于汇点的流入量，对于最大流问题既是要找出流入汇点的最大流量值。

求最大流的算法：

EK算法：EK算法中涉及的三个关键词：残留网络，增广路，割。

残留网络，假定我们已经找到了一个可行的流，那么对于每条边如果流量小于容量则表示该条边有剩余，以流的流量我们也可以看成是反向的残留，得到一个残留网络。

增广路：在残留网络中如果可以找到一条从源点到汇点的路，即为增广路，我们就可以将流值增加这条增广路上的最小边。

EK算法就是在残留网络中寻找增广路使得流值不断增大，直至达到最大为止。

Ek算法由于在寻找增广路时具有盲目性，算法效率不高。

Dinic算法：基于EK算法的思想，再从源点到汇点做bfs来寻找路时，对各点标一个层次值表示从源点到该点所需的最小步数，然后在这些层次的基础上做dfs，dfs的时候只能到其下一层的点，且容量需要比已流流量大，然后重复上述过程即可得到解。

最大流和最小割，如果我们想要把一个网络分成两部分，一部分包含源点s，另一部分包含汇点t，我们把这个集合之间，从源集合到汇集合之间的正向流量之和，称为是网络的割，而一个网络的割中最小的那个，我们称之为最小割。

最大流最小割定理：一个网络的最小割等于最大流。

最小费用最大流：在保证最大流的情形下，网络中的边，可能不只有流量还有费用，那么如果我们一方面希望网络拥有最大流，另一方面我们要求费用达到最小，这就是一个费用流的问题了，对于费用流的问题，事实上我们可以这么考虑，首先我们必须要找到的是最大流，另一方面我们需要费用最小，而在找最大流的时候我们总是在寻找增广路来增广，来使得我们能得到一个比现在更大的流，那么另一方面要求费用最小，所以我们可以在寻找增广路的时候找一条费用最小路来增广，而费用我们也可以看成是距离类的东西，也就是这样的话，我们可以用最短路，来找出这样一个最小费用的路来进行增广，而不断增广，即可得到最大流，这样我们就可以得到最小费用最大流。

网络流和费用流中经常会涉及到拆点的操作，将一个点分成入和出，来拆成两个点。例如联合训练赛的第六场第一个题目tour，给出一张图，要求将这个图划分成几个集合，要求每个集合的点的个数大于等于2，要求这个集合所有点可以构成一个环。图中的每条边都有一个边权，最后找到各个集合的总花费为所有构成环的边的权之和。要求这个花费最小。分析题目可以知道，我们最后分成各个集合之后一定是每个点的出度和入度都为1，所以这个题经过拆点之后就是最小权匹配问题，用km算法即可解决，当然我们也可以将它转化成一费用流问题，将图中的每个节点都拆成入和出两个点，增加源和汇，源点到进入的点连一条费用为0，流量为1的边，从出点到汇连一条费用为0，流量为1的边，原图中的边都练成费用为边权，流量为1的边 ，最后只要求这个网络的最小费用流即可。另外对于一些题是点权而不是边权的题目，也可以通过拆点来将点权转化成边权。所以拆点的想法在网络流中十分重要。

Question1：n个人围着一个桌子坐，每个人都有一个需求，假如一个人的需求是1，2，就表示他希望1，2坐在他的两边，若每个人的需要都可以满足，则我们需要求出 最少移动几个人可以达到每个人的要求都满足的状态（假定一开始的座位顺序为1，2，3，4，……，n）

分析：我们可以通过dfs找到一条闭合的回路即最终的状态，要想求出最少移动人数实际上就要找出最小的错排数，由于是圆桌旋转会出现另外的最优状态，所以一方面我们可以通过从每一个位置开始做起始点求一遍错排数，然后求出最小的错排数即为结果，但是这样做的复杂度是O(n^2)在题目（10^6）的数据范围下时间是难以承受的。

策略：分析中提到我们需要找出以各个点做起始点不同的错排的数目，事实上我们只要记录每个点它在哪一个位置在起始状态下是正确排的就可以了，这样的话我们就可以得到在不同起始状态下正确点的个数，即可以得到错排数。所以我们只需要扫描一遍，若一个点离它正确位置为k，即它在旋转了k个数的状态下是正确排列的，所以cnt[k]++,最后n-max(cnt[k])即为题目的解。

                                                                讲题人：rupxup

Question2：对于a,b,e,f整四个整数求最小的整数c使得存在d满足a/b<c/d<e/f.

分析：由题目可知事实上在c最小的情况下，也可以找到一个最小的d，这两个问题是相通的，我们先看两种特殊的情况：

a：a/b<1<e/f则存在c=1，d=1为题的解。

b：a/b=0，则存在c=1,d=f/e的下取整+1为题的解。

策略：对于上述两种特殊情况可以直接给出解，需要看其它情况可不可能转化成这两种特殊的情况，1.对于1<a/b<e/f,对于这种情况我们可以通过将等式两边同时减去这个整数来转化，可能出现上述a那种特殊状态，则得解c=1+k*d,d=1,即c=1+k;也有可能得到下述情况2.

2.对于a/b<e/f<1的情况可以通过求倒数之后化作1的情况，故1，2两种非特殊情况可以相互转化而且必然会转化到某一个特殊的状态，不断的在减，如果中间没有达到特殊状态a，也一定会达到特殊状态b的。

                                                                讲题人：rupxup

Question3:一只蚂蚁在一个木棍上爬，若这个蚂蚁的速度为v，木棍每分钟长长m，（相对的长长，向两端长长，蚂蚁的相对位置会保持，如原先在1/2处长长后蚂蚁还是在木棍1/2处），给出v和m和原始木棍长l，问是否蚂蚁是否有可能从最开始的一端爬到另一端。

题解：蚂蚁在木棍上的比例是不变的，只要蚂蚁在前进的过程中速度大于0，比例总是在增加，它就一定能爬到另一端。

                                                               讲题人：Abbie

Question4：给出原来有V升水，淘衣服上的洗衣粉，最多可以把洗衣粉分成n份，每次淘完还会残留b升脏水，问最多淘多少次，可以使得残留最少。

题解：事实上n次的时候残留最少，这是一个不断稀释的过程，用同样多的水稀释溶液，这个次数进行的越多，最后的溶液越稀。

PS：其实洗衣服可以多淘几次少用水的。

                                                                 讲题人：Abbie

Question5：笔记本放置问题，给你一个方桌，一个矩形，问最少覆盖多少桌面能把这个矩形放到桌面上。

策略：让矩形的中心位于方桌的一个角上所覆盖的面积会最小。

                                                                讲题人：Abbie

Question6：一遍dfs求强联通分量。我们在求强联通分量时，一般是把原图做一遍dfs，记录下各个点的访问结束时间，然后以访问结束时间的降序，将反向图做一遍dfs。下面是一种可以一遍dfs求出强联通分量的算法。

相关内容：我们在求一个图中的割点割边时，用一个数组dep表示点的访问时间，数组low表示其儿子可以到达的最浅位置，若low[v]>=dep[u](其实也是low[u]>=dep[u])时该点是割点，这么说实际上割点的low和dep相等，我们考虑一个图，若一个点是割点，则说明其儿子可以到达的最小深度也为它，这么说事实上它的这些儿子是可以通过它相互可达的。所以对于一个割点构成的分量若low值都等于割点的dep值，则这可以构成一个强联通分量。

PS:不是太懂。

                                                                讲题人：brent

Question7:单调队列在dp中的运用。

一些时候我们的dp方程中会出现一个值与它之前的多个值相关，这时候很多情况下会出现重复计算问题，比如每个数与它上个状态的它的前面所有状态有关，则我们每次都要从头来枚举这些值，事实上我们进行了比较之后可以记录当前的最优值，下次只需要比较最优值和新增值即可。对于有限定如和它前k个数有关，我们就可以用单调队列，来使用O(1)的时间来随时得到这个最大值。

对于一个连通图，删去某个点（删去一个点即把该点和与该点相邻接的边都删去）的集合得到的图将不再连通，删去该集合的任意子集该图依然连通，则称其为该图的一个点割集，若该集合只有一个点组成，则称其为割点。

同样对于一个连通图删去某个边的集合（删去一条边仅删去该条边即可）得到的图将不再连通，删去该边集合的任意子集该图依然连通，则称其为该图的边割集，若该集合只有一条边组成，则称其为割边即桥。

求割边割点最直接的方法就是按照定义，删去点或边然后对图进行遍历，看是否仍连通，但要求一个图的割点割边对整个图的每个点和每条边都需要做一下试探，时间复杂度太高。

求割边割点的过程，以某一个点开始做dfs，采用数组low[i],dep[i]表示一个节点可以到达的除其父亲外的最早被访问的点，dep表示该点的深度。

若有节点u有子节点v，且low[v]>=dep[u]则点u是割点。

若有low[v]>dep[u]则边(u,v)为割边.

 1int low[MAX],dep[MAX],mark[MAX],cutpoint[MAX];
 2void dfs(int s,int father,int depth)
 3{
 4   int u,v,tot=0;
 5   mark[s]=1;
 6   low[s]=dep[s]=depth;
 7   for(int i=0;i<mp[s].size();i++)
 8   {
 9      v=mp[s][i];
10      if(mark[v]==1&&v!=father&&dep[v]<low[s])
11      low[s]=dep[v];
12      else if(mark[v]==0) 
13      {
14         tot++;
15         dfs(v,s,depth+1)
16         if(low[v]<low[s])
17         low[s]=low[v];
18         if((s==root&&tot>1)||(s!=root&&low[v]>=dep[s]))
19         cutpoint[s]=1;
20         if(low[v]>dep[s])
21         //标记边（s，v）为割边 
22      }
23   }
24   mark[s]=2;
25}
26
27

对于一个有向图，有点u到点v可达，不一定意味着v到u可达，对于一个有向图，如果任意两点间都相互可达，则该图称为一个强连通图。若任意两点间要么u可达v，要么v可达u则称该图为单侧连通图。若去掉有向图的方向后为一个连通图则为弱连通图。对于一个图，若其不是强连通图，但是总可以找到它的连通分量，使得联通分量的点都是相互可达的，对于极大的连通分量即为图的强连通分量（Strongly Connected Component, SCC)，类似的有图的单侧连通分量，和弱连通分量。求一个图的弱连通分量，只需要用dfs或者bfs对图做一下遍历即可，有几棵树就有几个弱连通分量。对于求单侧连通分量，？？？？。对于求有向图的强连通分量有以下算法：

1.      对有向图以某个节点做dfs记录各点的结束时间。

2.      将图所有边反向，以结束时间从大到小，再做一遍dfs，如果从某个点可以遍历到一些点，则这些点可以构成一个强连通分量。

SCC求强连通分量的伪代码(邻接表表示，且同时完成了缩点操作，缩点时一般还需要对一些量进行特殊设定，需要在缩点时进行修改，该题是缩点时记录新节点包括旧图中的几个节点。)

vector<int>v1[MAX]; //原图
vector<int>v2[MAX]; //反向边图
int mark[MAX],Stack[MAX];
int Num[MAX],Nn[MAX];
int dep;
void dfs1(int i)
{
   mark[i]=1;
   for(int j=0;j<v1[i].size();j++)
      if(!mark[v1[i][j]])
      dfs1(v1[i][j]);
   Stack[dep++]=i;   
}
void dfs2(int i)
{
   Num[i]=cnt;
   Nn[cnt]++;
   mark[i]=1;
   for(int j=0;j<v2[i].size();j++)
      if(!mark[v2[i][j]])
      dfs2(v2[i][j]);      
}
void scc()//两边dfs
{
   int i,j;
   dep=1;
   memset(mark,0,sizeof(mark));
   for(i=1;i<=n;i++)
      if(!mark[i])
      dfs1(i);
   memset(mark,0,sizeof(mark));
   cnt=0;
   for(i=n;i>0;i--)
      if(!mark[Stack[i]])
      {
         cnt++;
         dfs2(Stack[i]);
      }
}

ps:因为一小点错，错了一下午，刷了一片wrong answer。还好最后这个小问题还是被我给发现了。
坚持就是胜利啊。*/

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

struct seg
{
       int x,y1,y2;
       int flag;
       seg(){}
       seg(int _x,int _y1,int _y2,int _f): x(_x),y1(_y1), y2(_y2), flag(_f){}
       bool operator < ( const seg& a) const
       {
            return x < a.x;
       }
}Edge[40005];
int f[600005];
int m[600005];
void update(int left,int right,int step)
{
    if(left==right-1)
    {
        if(f[step]>0)
        m[step]=1;
        else
        m[step]=0;
        return ;
    }
     if(f[step]>0)
     m[step]=right-left;
     else
     m[step]=m[2*step]+m[step*2+1];
}

void Buildtree(int left,int right,int l,int r,int c,int step)
{
    if(left==right-1)
    {
        f[step]+=c;
        update(left,right,step);
        return ;
    }
    if(left==l&&right==r)
     {
          f[step]+=c;
          update(left,right,step);
          return ;
     }
     else
     {
         int mid=(left+right)>>1;
         if(r<=mid)
         Buildtree(left,mid,l,r,c,2*step);
         else if(l>=mid)
         Buildtree(mid,right,l,r,c,2*step+1);
         else
         {
           Buildtree(left,mid,l,mid,c,2*step);
           Buildtree(mid,right,mid,r,c,2*step+1);
         }
         update(left,right,step);
         return ;
     }
}

int main()
{
    int t,n,x1,y1,x2,y2,i,j,my,pre;
    long long ans;
    scanf("%d",&t);
    while(t--)
    {
            scanf("%d",&n);
            memset(f,0,sizeof(f));
            memset(m,0,sizeof(m));
            j=my=0;
            for(i=0;i<n;i++)
            {
                 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                 if(x1==x2)
                 {
                           if(y1>y2) swap(y1,y2);
                           Edge[j++]=seg(x1-1,y1,y2,1);
                           Edge[j++]=seg(x1+1,y1,y2,-1);
                 }
                 else if(y1==y2)
                 {
                          if(x1>x2) swap(x1,x2);
                          Edge[j++]=seg(x1,y1-1,y1+1,1);
                          Edge[j++]=seg(x2,y1-1,y1+1,-1);
                 }
                 my=max(y2,my);
            }
            sort(Edge,Edge+j);
            ans=0;
            pre=Edge[0].x;
            for(i=0;i<j;i++)
            {
                   ans+=m[1]*(Edge[i].x-pre);
                   Buildtree(0,my+2,Edge[i].y1,Edge[i].y2,Edge[i].flag,1);
                   pre=Edge[i].x;
            }
              cout<<ans<<endl;
    }
    return 0;
}