[图论][欧拉路径][特判] codeforces 1038E Maximum Matching

http://codeforces.com/contest/1038/problem/E

“这题有点难受”系列。之所以能这么O(n)做完全是有且仅有4个点，玄学。

其实也不是很难受，主要是最后一组测试(test 117)让我意识到原来的处理方法对于那种特殊情况都不适用，然后感觉在这时候只能用n²算法才能解决。。。想了很久反正是，最后终于发现当（奇点数==4&&删去最小边会使得4个点不联通）这种情况只有两种，一种是三个点连成环然后剩下一个挂在外面，另一种是1到2和3到4有1条边，而2到3有两条，所以只要把这两种情况特殊判断一下就还是O(n)的算法了。。

正经地说：把1234看成4个点，n个block相当于边，题目意思就是找出一条最长的路使得每条路都只能走一次，无向图只能走一次，很显然的欧拉路径的操作。但是要分很多情况讨论。

首先分连通分量有几个的时候，当有2，3，4个的时候就是找到这几个连通分量中的最大值，因为这时候每个联通分量都一定是有欧拉路径的，3的时候可能比较难证明，但是可以通过4个点组成的图奇点只有024三种可能推出来。

然后当只有一个连通分量也就是四个点都联通的时候，讨论奇点数量，前面已经说过奇点数量只可能是024，当是02的时候直接全选因为一定有欧拉路径，当是4的时候再分类讨论：找权值最小的那条边，看他是不是去掉后会使得多出来一个连通分量，说是多出来一个联通分量其实只有可能是多出来一个孤立的点，因为其他情况都与（4个点都是奇点）这个条件相矛盾，所以删除这条边如果能使得原图不连通那么一定是分成了一个3个点一个1个点，这里面又有两种具体的情况，也就是之前说的，一种只有一个桥另一种有两个桥，如果不是这两种情况那么直接取全部的边然后删除掉最小权值边，如果是这两种情况则单独特判即可。。需要注意的是这两种情况需要循环一遍所有的边来确定最大值，因为删除的可能是其他的边也可能是桥。

#include

using namespace std;

typedef long long LL;
const int maxn=5e5+5;
const int mod=1e9+7;

int mi[17][17];

int p[5],deg[5];
int find(int x)
{
    return x==p[x]?x:p[x]=find(p[x]);
}
int edges[105][3];
LL self[5];

int main()
{
    for (int i=1; i<=4; i++)
        p[i]=i;
    int n,u,v,c,f1,f2,cnt=4,odd=0;
    LL ans=0;
    int gmi=1e6+10;
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        //cin>>u>>c>>v;
        scanf("%d%d%d",&u,&c,&v);
        edges[i][0]=u,edges[i][1]=c,edges[i][2]=v;
        ans+=c;
        if(u!=v)
        {
            mi[u][v]++,mi[v][u]++;
            gmi=min(gmi,c);
            deg[u]++,deg[v]++;
            f1=find(u),f2=find(v);
            if(f1!=f2)
            {
                p[f1]=f2;
                cnt--;
            }
        }
        else
        {
            self[u]+=c;
        }
    }
    for(int i=1; i<=4; i++)
        if(deg[i]&1)
            odd++;
    if(cnt==1)
    {
        if(odd==4)
        {
            int flag=0;
            int fd=5;
            for (int i=1; i<=n; i++)
                if(gmi==edges[i][1])
                {
                    if(mi[edges[i][0]][edges[i][2]]!=1)
                    {
                        flag=1;
                        break;
                    }

                }
            if(flag)
                cout<S;
                for (int i=1;i<=4;i++)
                    if(deg[i]==1)S.insert(i);

                if(S.size()==1)
                {
                    int cn=*S.begin(),ce;
                    gb=self[*S.begin()];
                    for(int i=1;i<=n;i++)
                    {
                        if(edges[i][0]!=edges[i][2])
                        {
                            if(edges[i][0]==cn||edges[i][2]==cn)
                            {
                                ce=i;
                                break;
                            }
                        }
                    }
                    gb=max(gb,ans-edges[ce][1]-gb);
                    for (int i=1;i<=n;i++)if(i!=ce&&edges[i][0]!=edges[i][2])
                    {
                        gb=max(gb,ans-edges[i][1]);
                    }
                }
                else if(S.size()==2)
                {
                    int ce1=0,ce2=0,cn1=*S.begin();S.erase(S.begin());
                    int cn2=*S.begin();
                    for(int i=1;i<=n;i++)
                    {
                        if(edges[i][0]!=edges[i][2])
                        {
                            if(edges[i][0]==cn1||edges[i][2]==cn1)
                                ce1=i;
                            if(edges[i][0]==cn2||edges[i][2]==cn2)
                                ce2=i;
                            if(ce1&&ce2)
                                break;
                        }
                    }
                    gb=max(self[cn1],ans-self[cn1]-edges[ce1][1]);
                    gb=max(gb,max(self[cn2],ans-self[cn2]-edges[ce2][1]));
                    for (int i=1;i<=n;i++)if(i!=ce1&&i!=ce2&&edges[i][0]!=edges[i][2])
                        gb=max(gb,ans-edges[i][1]);
                }
                cout<