图论模板

求桥

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
/*
*  求 无向图的割点和桥
*  可以找出割点和桥，求删掉每个点后增加的连通块。
*  需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重
*/
const int MAXN = 10010;
const int MAXM = 100010;
struct Edge
{
    int to,next;
    bool cut;//是否为桥的标记
}edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int Index,top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];//删除一个点后增加的连通块
int bridge;
 
void addedge(int u,int v)
{
    edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false;
    head[u] = tot++;
}
void Tarjan(int u,int pre)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    int son = 0;
    for(int i = head[u];i != -1;i = edge[i].next)
    {
        v = edge[i].to;
        if(v == pre)continue;
        if( !DFN[v] )
        {
            son++;
            Tarjan(v,u);
            if(Low[u] > Low[v])Low[u] = Low[v];
            //桥
            //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。
            if(Low[v] > DFN[u])
            {
                bridge++;
                edge[i].cut = true;
                edge[i^1].cut = true;
            }
            //割点
            //一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。
            //(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，
            //即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)
            if(u != pre && Low[v] >= DFN[u])//不是树根
            {
                cut[u] = true;
                add_block[u]++;
            }
        }
        else if( Low[u] > DFN[v])
             Low[u] = DFN[v];
    }
    //树根，分支数大于1
    if(u == pre && son > 1)cut[u] = true;
    if(u == pre)add_block[u] = son - 1;
    Instack[u] = false;
    top--;
}
 
void solve(int N)
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(add_block,0,sizeof(add_block));
    memset(cut,false,sizeof(cut));
    Index = top = 0;
    bridge = 0;
    for(int i = 1;i <= N;i++)
        if( !DFN[i] )
            Tarjan(i,i);
    printf("%d critical links\n",bridge);
    vector<pair<int,int> >ans;
    for(int u = 1;u <= N;u++)
        for(int i = head[u];i != -1;i = edge[i].next)
            if(edge[i].cut && edge[i].to > u)
            {
                ans.push_back(make_pair(u,edge[i].to));
            }
    sort(ans.begin(),ans.end());
    //按顺序输出桥
    for(int i = 0;i < ans.size();i++)
        printf("%d - %d\n",ans[i].first-1,ans[i].second-1);
    printf("\n");
}
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
//处理重边
map<int,int>mapit;
inline bool isHash(int u,int v)
{
    if(mapit[u*MAXN+v])return true;
    if(mapit[v*MAXN+u])return true;
    mapit[u*MAXN+v] = mapit[v*MAXN+u] = 1;
    return false;
}
int main()
{
    int n;
    while(scanf("%d",&n) == 1)
    {
        init();
        int u;
        int k;
        int v;
        //mapit.clear();
        for(int i = 1;i <= n;i++)
        {
            scanf("%d (%d)",&u,&k);
            u++;
            //这样加边，要保证正边和反边是相邻的，建无向图
            while(k--) 
            {
                scanf("%d",&v);
                v++;//保证点从1开始;
                //if(v <= u)continue;
                //if(isHash(u,v))continue;
                addedge(u,v);
                addedge(v,u);
            }
        }
        solve(n);
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int vis[100009];
int a[100009];
int cnt;
const int maxn=100000+10;
pair<int, int>ans[maxn];
int dfs_clock;//时钟，每访问一个节点增1
vector<int> G[maxn];//G[i]表示i节点邻接的所有节点
int pre[maxn];//pre[i]表示i节点被第一次访问到的时间戳,若pre[i]==0表示i还未被访问
int low[maxn];//low[i]表示i节点及其后代能通过反向边连回的最早的祖先的pre值
bool iscut[maxn];//标记i节点是不是一个割点
//求出以u为根节点(u在DFS树中的父节点是fa)的树的所有割顶和桥
//初始调用为dfs(root,-1);
int dfs(int u,int fa)
{
    int lowu=pre[u]=++dfs_clock;
    int child=0;    //子节点数目
    for(int i=0; i<G[u].size(); i++)
    {
        int v=G[u][i];
        if(!pre[v])
        {
            child++;//未访问过的节点才能算是u的孩子
            int lowv=dfs(v,u);
            lowu=min(lowu,lowv);
            if(lowv>pre[u])
            {
                iscut[u]=true;      //u点是割顶
                ans[++cnt] = make_pair(min(u,v), max(u,v));
                //保证从小到大的顺序输出
                //这里的边用pair来表示，便于后续输出；
                //printf("边(%d, %d)是桥\n",u,v);
            }
        }
        else if(pre[v]<pre[u] && v!=fa)//=fa确保了(u,v)是从u到v的反向边
        {
            lowu=min(lowu,pre[v]);
        }
    }
    if(fa<0 && child==1 )
        iscut[u]=false;//u若是根且孩子数<=1,那u就不是割顶
    return low[u]=lowu;
}
 
int main()
{
    int t;
    cin>>t;
    int kk=1;
    while(t--)
    {
        //t组测试样例
        cnt=0;
        dfs_clock=0;//初始化时钟
        memset(pre,0,sizeof(pre));
        memset(iscut,0,sizeof(iscut));
        memset(vis,0,sizeof(vis));
        int n;
        cin>>n;
        for(int i=0; i<n; i++)
        {
            G[i].clear();
        }
        for(int i=1; i<=n; i++)
        {
            int point;
            cin>>point;
            char a,b;
            int tot;
            cin>>a>>tot>>b;
            for(int j=1; j<=tot; j++)
            {
                int uu;
                cin>>uu;
                G[point].push_back(uu);
                G[uu].push_back(point);
            }
        }
        printf("Case %d:\n",kk++);
        for(int i=0; i<n; i++)
        {
            if(pre[i]==0)//图可能不连通，所以要这样！
                dfs(i,-1);//初始调用
        }
        sort(ans+1, ans+1+cnt);
        printf("%d critical links\n",cnt);
        for(int i=1; i<=cnt; i++)
        {
            cout << ans[i].first << " - " << ans[i].second << endl;
 
        }
 
 
    }
    return 0;
}
/*
9 11
0 1
1 2
2 3
3 4
0 4
1 4
0 5
5 6
5 7
5 8
7 8
下面是输出
边(5, 6)是桥
边(0, 5)是桥
割顶是:0
割顶是:5
1 2 3 4 5 6 7 8 9
1 1 1 1 1 6 7 6 6
*/

 割点

#include<bits/stdc++.h>
using namespace std;
const int maxn=150;
int n;
struct node
{
	int to;
	int next;
}edge[maxn*maxn];
int head[maxn];
int index;
int tot;
int low[maxn];
int DFN[maxn];
bool instack[maxn];
bool cut_point[maxn];
 
void init()
{
	tot=0;
	index=0;
	memset(head,-1,sizeof(head));
	memset(cut_point,0,sizeof(cut_point));
	memset(instack,0,sizeof(instack));
}
 
void addedge(int from,int to)
{
	edge[tot].to=to;
	edge[tot].next=head[from];
	head[from]=tot++;
}
 
void tarjan(int u,int root,int fa)
{
	DFN[u]=low[u]=++index;
	instack[u]=1;
	int cnt=0;
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(!instack[v])
		{
			tarjan(v,root,u);
			cnt++;
			if(low[u]>low[v])
		 		low[u]=low[v];
 			if(u==root && cnt>1)
 				cut_point[u]=1;
			else if(u!=root && low[v]>=DFN[u])
				cut_point[u]=1;
		}
		else if(v!=fa && low[u] > DFN[v])
			low[u]=DFN[v];
	}
}
 
int search_cut_point()
{
	int ans=0;
	tarjan(1,1,-1);
	for(int i=1;i<=n;i++)
		if(cut_point[i])
			ans++;
	return ans;
}
 
int main()
{
	while(~scanf("%d",&n) && n)
	{
		init();
		int s,t;
		while(scanf("%d",&s) && s)
		{
			while(getchar()!='\n')
			{
				scanf("%d",&t);
				addedge(s,t);
				addedge(t,s);//加边;
			}
		}
		printf("%d\n",search_cut_point());//进行计算;
	}
	return 0;
}

求LCA

#include <bits/stdc++.h>
using namespace std;
 
const int maxn=10010;//顶点数
const int maxq=100;//最多查询次数，根据题目而定，本题中其实每组数据只有一个查询.
 
//并查集
int f[maxn];//根节点
int find(int x)
{
    if(f[x]==-1)
        return x;
    return f[x]=find(f[x]);
}
void unite(int u,int v)
{
    int x=find(u);
    int y=find(v);
    if(x!=y)
        f[x]=y;
}
//并查集结束
 
bool vis[maxn];//节点是否访问
int ancestor[maxn];//节点i的祖先
struct Edge
{
    int to,next;
}edge[maxn*2];
int head[maxn],tot;
void addedge(int u,int v)//邻接表头插法加边
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
 
struct Query
{
    int q,next;
    int index;//查询编号，也就是输入的顺序
}query[maxq*2];
int ans[maxn*2];//存储每次查询的结果,下表0~Q-1，其实应该开maxq大小的。
int h[maxn],tt;
int Q;//题目中需要查询的次数
 
void addquery(int u,int v,int index)//邻接表头插法加询问
{
    query[tt].q=v;
    query[tt].next=h[u];
    query[tt].index=index;
    h[u]=tt++;
    query[tt].q=u;//相当于两次查询，比如查询  3，5 和5，3结果是一样的，以3为头节点的邻接表中有5，以5为头节点的邻接表中有3
    query[tt].next=h[v];
    query[tt].index=index;
    h[v]=tt++;
}
 
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
    tt=0;
    memset(h,-1,sizeof(h));
    memset(vis,0,sizeof(vis));
    memset(f,-1,sizeof(f));
    memset(ancestor,0,sizeof(ancestor));
}
 
void LCA(int u)
{
    ancestor[u]=u;
    vis[u]=true;
    for(int i=head[u];i!=-1;i=edge[i].next)//和顶点u相关的顶点
    {
        int v=edge[i].to;
        if(vis[v])
            continue;
        LCA(v);
        unite(u,v);
        ancestor[find(u)]=u;//将u的左右孩子的祖先设为u
    }
    for(int i=h[u];i!=-1;i=query[i].next)//看输入的查询里面有没有和u节点相关的
    {
        int v=query[i].q;
        if(vis[v])
            ans[query[i].index]=ancestor[find(v)];
    }
}
bool flag[maxn];//用来确定根节点的
int num[100006];
int t;
int n,u,v;
 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&Q);
        init();
        memset(flag,0,sizeof(flag));
        memset(num,0,sizeof(num));
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            flag[v]=true;//有入度
            addedge(u,v);
            addedge(v,u);
        }
      //  Q=1;//题目中只有一组查询
 
        for(int i=0;i<Q;i++)
        {
            scanf("%d%d",&u,&v);
            addquery(u,v,i);
            num[i]=u;
        }
        int root;
        for(int i=1;i<=n;i++)
        {
            if(!flag[i])
            {
                root=i;
                break;
            }
        }
        LCA(root);
        for(int i=0;i<Q;i++)
            {
                if(num[i]==ans[i])printf("YES\n");
                else printf("NO\n");
            }
    }
 
    return 0;
}

最小生成树并查集优化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 110000
struct node
{
    int u,v;
    int w;
}edge[maxn];
int n,m,fa[maxn];
int cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void kruskal(int n,int m)
{
    for(int i=1;i<=n;i++)fa[i]=i;
    int ans=0;
    int cnt=0;
    sort(edge,edge+m,cmp);
    for(int k=0;k<m;k++)
    {
        int x=find(edge[k].u),y=find(edge[k].v);
        if(x!=y)
        {
            cnt++;
            fa[x]=y;
            ans+=edge[k].w;
            if(cnt==n-1)
            {
                break;
                ;
                ;
                ;
                ;
            }
        }
    }
   printf("%d\n",ans);
}
int x[maxn],y[maxn];
int main()
{
    while(scanf("%d",&n)&&n)
    {
        m=n*(n-1)/2;
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            edge[i].u=a;
            edge[i].v=b;
            edge[i].w=c;
        }
        kruskal(n,m);
    }
    return 0;
}

最短路+优先队列

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll M=100000000000;
struct HeadNode
{
    ll d,u;
    ll dist;////////-0---------0-
    bool operator < (const HeadNode& rhs) const
    {
        if(d>rhs.d)
            return 1;
        else if(d==rhs.d&&dist>rhs.dist)
            return 1;
        return 0;//
    }
};
struct edge
{
    ll from;
    ll to;
    ll time;
    ll dist;
    ll next;
} edge[300005];
ll head[300005];
ll num=0;
void add_edge(ll from,ll to,ll time,ll dist)
{
    edge[num].from = from;
    edge[num].to = to;//终点
    edge[num].time=time;//权值
    edge[num].dist=dist;
    edge[num].next=head[from];//记录以from节点出发的上一条边在edge数组的位置
    head[from]=num;  //更新以from节点出发的在edge数组的位置
    num++; //数组下标+1
}
bool vis[300005];
ll n,m,x,s,t;
ll d[300005];
ll cost[300005];//--
void Dij()
{
    d[s]=0;
    cost[s]=0;//
    priority_queue<HeadNode>Q;
    while(!Q.empty())
        Q.pop();//
    Q.push((HeadNode)
    {
        0,s,cost[s]
    });
    while(!Q.empty())
    {
        HeadNode x=Q.top();
        Q.pop();
        ll u=x.u;
        if(vis[u])
            continue;
        vis[u]=1;
        for(ll i=head[u]; i!=0; i=edge[i].next)
        {
            ll to=edge[i].to;
            ll time=edge[i].time;
            ll dist=edge[i].dist;
            if(d[to]>d[u]+time)
            {
                d[to]=d[u]+time;//---
                cost[to]=dist;//ttt
                Q.push((HeadNode)
                {
                    d[to],to,cost[to]
                });
            }
            else if(d[to]==d[u]+time&&cost[to]>dist)
            {
                cost[to]=dist;//---///--
                Q.push((HeadNode)
                {
                    d[to],to,cost[to]
                });
            }
        }
 
    }
}
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        num=1;
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        memset(edge,0,sizeof(edge));
        scanf("%lld %lld",&n,&m);//---
        s=1;
        for(ll i=1; i<=n; i++)
        {
            d[i]=M;
            cost[i]=M;
        }
        for(ll i=1; i<=m; i++)
        {
            ll x,to,time,dist;
            scanf("%lld %lld",&x,&to);//---
            x++;
            to++;
            scanf("%lld %lld",&time,&dist);
            add_edge(x,to,time,dist);
            add_edge(to,x,time,dist);
        }
        Dij();
        ll ans1=0;
        ll ans2=0;
        for(ll i=1; i<=n; i++)
        {
            ans1+=d[i];
            ans2+=cost[i];
        }
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}

Prim最小生成树

#include <iostream>  
#include <algorithm>   
#include <string.h> 
#include <queue> 
using namespace std;  
const int inf=0x3f3f3f3f;;
const int maxx=1e3+100;;
const int maxn=2e6+10;
typedef long long ll;
int m,n,q,ans,sum;  
int dis[maxx];
int sto[maxx];
int head[2*maxn];
bool vis[maxx]; 
int a[maxx][maxx];
struct  point{    
    int to;  
    int next; 
	int val; 
	bool operator < (const point &a) const
	{
		return val>a.val;
	}
};  
point pt[2*maxn]; 
void add(int u,int v,int val)
{
	      pt[q].next=head[u];  
          pt[q].to=v;
		  pt[q].val=val;
		  head[u]=q++;
} 
void prim(int st)  
{  
    priority_queue<point>q;
    point t1,t2;
	int w,v;
    memset(dis,inf,sizeof(dis));
    memset(vis,false,sizeof(vis));
    for (int i=head[st];i!=-1;i=pt[i].next)
    {
    	 int v=pt[i].val;
    	 if (dis[pt[i].to]>v)
    	 {
    	 	dis[pt[i].to]=v;
    	 	t1.to=pt[i].to;
    	 	t1.val=v;
    	 	q.push(t1);
		 }
	}
	vis[st]=true;
	ans=1;sum=0;
	while (!q.empty())
	{
		point t=q.top();
		q.pop();
		int v=t.to;
		if (vis[v])continue;
		vis[v]=true;
		sum+=dis[v];
		ans++;
		for (int i=head[v];i!=-1;i=pt[i].next)
		{
			 int u=pt[i].to;
			 if (!vis[u]&&pt[i].val<dis[u])
			 {
			 	dis[u]=pt[i].val;
			 	t2.to=u;
			 	t2.val=pt[i].val;
			 	q.push(t2);
			 }
		}
	}
}
int main()
{
	int k,u,v,val,st;
	cin>>m>>n>>k;
	memset(head,-1,sizeof(head));
	q=1;
	for (int i=0;i<m;i++)
	{
		cin>>u>>v>>val;
		add(u,v,val);
		add(v,u,val);
		st=u;
	}
    prim(st); 
    if (ans==n)
    cout<<sum<<endl;
    else
    cout<<"don't exit "<<endl; //没有
	return 0;
}

 欧拉：

有向图欧拉通路充要条件：D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1。

有向图欧拉回路充要条件：当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。

有向欧拉通路 

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=26+6;
int fa[maxn];
int in[maxn],out[maxn];
int m;//单词数
int findset(int u)
{
    if(fa[u]==-1)
        return u;
    return fa[u]=findset(fa[u]);
}
//入度=出度或有两个特殊节点，一个入度-出=1，一个反之 图联通
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(fa,-1,sizeof(fa));
        scanf("%d",&m);
        for(int i=0; i<m; i++)
        {
            char str[1200];
            scanf("%s",str);
            int len=strlen(str);
            int u=str[0]-'a', v=str[len-1]-'a';
            in[u]++;
            out[v]++;
            u=findset(u), v=findset(v);
            if(u!=v)
                fa[u]=v;
        }
        int cnt=0;
        for(int i=0; i<26; i++)
            if( (in[i]||out[i]) && findset(i)==i )
                cnt++;//注意这里是为了避免有些字母没有出现
        if(cnt>1)
        {
            printf("The door cannot be opened.\n");
            continue;
        }
        int c1=0, c2=0, c3=0;//分别表示入度!=出度时的三种情况
        for(int i=0; i<26; i++)
        {
            if(in[i]==out[i])
                continue;
            else if(in[i]-out[i]==1)
                c1++;
            else if(out[i]-in[i]==1)
                c2++;
            else
                c3++;
        }
        if( ( (c1==c2&&c1==1)||(c1==c2&&c1==0) )&&c3==0 )
            printf("Ordering is possible.\n");
        else
            printf("The door cannot be opened.\n");
    }
    return 0;
}

 

 无向图：

#include<bits/stdc++.h>
#define PI 3.1415926
 
using namespace std;
 
const int maxn = 1003;
int P,Q;   ///P为顶点数，Q为边数
int degree[maxn];  ///存放每个节点的度数
int father[maxn];  ///进行并查集操作的数组
void make_set()
{
    for(int i = 1; i <= P; i++)
    {
        father[i] = i;
    }
}
int find_set(int x)
{
    return father[x]==-1?x:father[x]=find_set(father[x]);
}
void union_set(int x,int y)
{
    father[x] = y;
}
bool IsConnection() ///判图是否连通
{
    int num = 0;
    for(int i = 1; i <= P; i++)
    {
        if(father[i]==-1)  ///自己所属集合是自己点只能有一个
            num++;
    }
    if(num == 1) return true;
    else return false;
}
int main()
{
    int N,A,B;
    cin>>N;
    while(N--)
    {
        memset(father,-1,sizeof(father));
        cin>>P>>Q;
        memset(degree,0,sizeof(degree));
        //make_set();  ///初始化并查集
        for(int i = 0; i < Q; i++)
        {
            scanf("%d%d",&A,&B);
            degree[A]++;
            degree[B]++;
            int fa = find_set(A);
            int fb = find_set(B);
            if(fa!=fb)
                union_set(fa,fb);
        }
        int num = 0;
        for(int i = 1; i <= P; i++)
        {
            if(degree[i]%2)  ///统计奇度节点的个数
                num++;
        }
        ///如果奇度节点的个数是0个或2个，且图是连通的则存在欧拉通路
        if((num==0||num==2)&&IsConnection())
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
//欧拉通路:图连通；图中只有2个度为奇数的节点(就是欧拉通路的2个端点)
//欧拉回路:图连通；图中所有节点度均为偶数
    return 0;
}

 

定义：

欧拉通路 (欧拉迹):通过图中每条边且只通过一次，并且经过每一顶点的通路。

欧拉回路 (欧拉闭迹):通过图中每条边且只通过一次，并且经过每一顶点的回路。

欧拉图:存在欧拉回路的图。

简单说欧拉通路就是首尾不相接，而欧拉回路要求首尾相接。

 

无向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通；图中只有2个度为奇数的节点(就是欧拉通路的2个端点)

欧拉回路:图连通；图中所有节点度均为偶数

 

有向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通；除2个端点外其余节点入度=出度；1个端点入度比出度大1；一个端点入度比出度小1

欧拉回路:图连通；所有节点入度=出度

拓扑排序

给你一个图，然后要求把度数小于2的点全部删去，然后问你奇数集合的点权和是多少

注意，你删去了一个点之后，可能会使得一些点又变成了度数小于2的

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
struct edge
{
    int v,next;
} edge[maxn*2];
int t,head[maxn];
int indeg[maxn],vis[maxn];
int x[maxn],y[maxn],father[maxn],sum[maxn];
ll val[maxn];
void inti()
{
    t=0;
    memset(head,-1,sizeof(head));
    memset(indeg,0,sizeof(indeg));
    memset(vis,0,sizeof(vis));
}
void add(int u,int v)
{
    edge[t].v=v;
    edge[t].next=head[u];
    head[u]=t++;
    indeg[v]++;
}
int que[maxn],b1,b2;
//拓扑排序；
void tuopu(int n)
{
    b1=b2=0;
    for(int i=1; i<=n; i++)
    {
        if(indeg[i]<=1)
        {
            vis[i]=1;//单独的一个点；
            que[b2++]=i;
        }
    }
    while(b1!=b2)
    {
        int temp=que[b1++];
        for(int i=head[temp]; i>-1; i=edge[i].next)
        {
            int to=edge[i].v;
            if(vis[to]==0)
            {
                indeg[to]--;
                if(indeg[to]==1)
                {
                    que[b2++]=to;
                    vis[to]=1;
                }
            }
        }
    }
}
int find(int x)
{
    if(x==father[x]) return x;
    return father[x]=find(father[x]);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        inti();
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&val[i]);
            father[i]=i;//为并查集作铺垫;
            sum[i]=1;//每个点都包含它本身
        }
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            add(x[i],y[i]);//加点；
            add(y[i],x[i]);//看成无向图；
        }
        tuopu(n);//进行拓扑排序；
        for(int i=0; i<m; i++)
        {
            if(vis[x[i]]==0&&vis[y[i]]==0)
            {
                int fx=find(x[i]);
                int fy=find(y[i]);
                if(fx!=fy)
                {
                    father[fx]=fy;//把fy当做父节点；
                    val[fy]+=val[fx];//加上子节点的val值
                    sum[fy]+=sum[fx];//便于看联通快数目是奇数偶数
                }
            }
        }
        ll res=0;
        for(int i=1; i<=n; i++)
        {
            if(father[i]==i&&vis[i]==0&&sum[i]&1) res=res+val[i];
            //是父节点且vis[i]=0并且所包含的个数是奇数，则累加；
        }
        printf("%I64d\n",res);
    }
    return 0;
}

求多边形内最短距离

#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fLL
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
int min3(int a,int b,int c)
{
    return min(min(a,b),c);
}
int max3(int a,int b,int c)
{
    return max(max(a,b),c);
}
int gcd(int x, int y)
{
    if(y==0)
        return x;
    return gcd(y, x%y);
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct Point
{
    double x, y, dis;
} pt[200005], stackk[200005], p0;
int top, tot;
//计算几何距离
double Dis(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
//极角比较， 返回-1: p0p1在p0p2的右侧，返回0:p0,p1,p2共线
int Cmp_PolarAngel(struct Point p1, struct Point p2, struct Point pb)
{
    double delta=(p1.x-pb.x)*(p2.y-pb.y)-(p2.x-pb.x)*(p1.y-pb.y);
    if (delta<0.0)
        return 1;
    else if (delta==0.0)
        return 0;
    else
        return -1;
}
// 判断向量p2p3是否对p1p2构成左旋
bool Is_LeftTurn(struct Point p3, struct Point p2, struct Point p1)
{
    int type=Cmp_PolarAngel(p3, p1, p2);
    if (type<0)
        return true;
    return false;
}
//先按极角排，再按距离由小到大排
int Cmp(const void*p1, const void*p2)
{
    struct Point*a1=(struct Point*)p1;
    struct Point*a2=(struct Point*)p2;
    int type=Cmp_PolarAngel(*a1, *a2, p0);
    if (type<0)
        return -1;
    else if (type==0)
    {
        if (a1->dis<a2->dis)
            return -1;
        else if (a1->dis==a2->dis)
            return 0;
        else
            return 1;
    }
    else
        return 1;
}
//求凸包
void Hull(int n)
{
    int i, k;
    p0.x=p0.y=inf;
    for (i=0; i<n; i++)
    {
        scanf("%lf %lf",&pt[i].x, &pt[i].y);
        if (pt[i].y < p0.y)
        {
            p0.y=pt[i].y;
            p0.x=pt[i].x;
            k=i;
        }
        else if (pt[i].y==p0.y)
        {
            if (pt[i].x<p0.x)
            {
                p0.x=pt[i].x;
                k=i;
            }
        }
    }
    pt[k]=pt[0];
    pt[0]=p0;
    for (i=1; i<n; i++)
        pt[i].dis=Dis(pt[i].x,pt[i].y, p0.x,p0.y);
    qsort(pt+1, n-1, sizeof(struct Point), Cmp);
    //去掉极角相同的点
    tot=1;
    for (i=2; i<n; i++)
        if (Cmp_PolarAngel(pt[i], pt[i-1], p0))
            pt[tot++]=pt[i-1];
    pt[tot++]=pt[n-1];
    //求凸包
    top=1;
    stackk[0]=pt[0];
    stackk[1]=pt[1];
    for (i=2; i<tot; i++)
    {
        while (top>=1 && Is_LeftTurn(pt[i], stackk[top], stackk[top-1])==false)
            top--;
        stackk[++top]=pt[i];
    }
}
//计算叉积
double CrossProduct(struct Point p1, struct Point p2, struct Point p3)
{
    return (p1.x-p3.x)*(p2.y-p3.y)-(p2.x-p3.x)*(p1.y-p3.y);
}
//卡壳旋转，求出凸多边形所有对踵点
double hl(double a,double b,double c)
{
    double p=(a+b+c)/2.0;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
double dist(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void Rotate(struct Point*ch, int n)
{
    int i, p=1;
    double t1, t2, ans=inf, dif;
    ch[n]=ch[0];
    for (i=0; i<n; i++)
    {
        //如果下一个点与当前边构成的三角形的面积更大，则说明此时不构成对踵点
        while (fabs(CrossProduct(ch[i],ch[i+1],ch[p+1])) > fabs(CrossProduct(ch[i],ch[i+1],ch[p])))
            p=(p+1)%n;
        dif=fabs(CrossProduct(ch[i],ch[i+1],ch[p+1])) - fabs(CrossProduct(ch[i],ch[i+1],ch[p]));
        //如果当前点和下一个点分别构成的三角形面积相等，则说明两条边即为平行线，对角线两端都可能是对踵点
        t1=hl(dist(ch[i],ch[i+1]),dist(ch[i+1],ch[p]),dist(ch[p],ch[i]))*2.0/dist(ch[i],ch[i+1]);
        //printf(">>%lf\n",dist(ch[i],ch[i+1]));
        if (t1<ans)
            ans=t1;
    }
    printf("%.16lf\n",ans);
}
int main (void)
{
    int n;
    while(scanf("%d%*d",&n)!=EOF)
    {
        memset(pt,0,sizeof(pt));
        memset(stackk,0,sizeof(stackk));
        Hull(n);
        Rotate(stackk, top+1);
    }
    return 0;
}

多个 

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<iostream>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
using namespace std;

const double pi=acos(-1.0);
#define ll long long
#define pb push_back

#define sqr(a) ((a)*(a))
#define dis(a,b) sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))

const double eps=1e-10;
const int maxn=5e4+56;
const int inf=0x3f3f3f3f;

struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator -(const Point &p){return Point(x-p.x,y-p.y);}
    bool operator<(const Point &a)const{
         if(x!=a.x)return x<a.x;
         else return y<a.y;
    }
    double dot(const Point&p){return x*p.x+y*p.y;}
    double det(const Point&p){return x*p.y-y*p.x;}
};
Point P[maxn],Q[maxn];

//AB与AC的叉积，正表示C在向量AB的逆时针方向
double cross(Point A,Point B,Point C){
    return (B-A).det(C-A);
}
//AB与AC的点积，0则垂直
double multi(Point A,Point B,Point C){
    return (B-A).dot(C-A);
}

void anticlockwise_sort(Point *p,int N){
    for(int i=0;i<N-2;i++){
        double tmp=cross(p[i],p[i+1],p[i+2]);
        if(tmp>eps)return;
        else if(tmp<-eps){
            reverse(p,p+N);return;
        }
    }
}

//C到线段AB的距离
double point_to_line(Point A,Point B,Point C){
    if(dis(A,B)<eps)return dis(B,C);
    if(multi(A,B,C)<-eps)return dis(A,C);
    if(multi(B,A,C)<-eps)return dis(B,C);
    return fabs(cross(A,B,C)/dis(A,B)); //面积
}
//两线段AB到CD的距离
double line_to_line(Point A,Point B,Point C,Point D){
    return min(min(point_to_line(A,B,C),point_to_line(A,B,D)),//四种可能
                min(point_to_line(C,D,A),point_to_line(C,D,B))
            );
}
//两凸包求距
//
double solve(Point *P,Point *Q,int n,int m){
    int yminP=0,ymaxQ=0;
    for(int i=0;i<n;i++)if(P[i].y<P[yminP].y)yminP=i;
    for(int i=0;i<m;i++)if(Q[i].y>Q[ymaxQ].y)ymaxQ=i;
    P[n]=P[0];Q[m]=Q[0];
    double arg,ans=inf;
    for(int i=0;i<n;i++){   //枚举p上的点
        while(arg=(cross(P[yminP+1],Q[ymaxQ+1],P[yminP]) - cross(P[yminP+1],Q[ymaxQ],P[yminP]))>eps){
            ymaxQ=(ymaxQ+1)%m;
        }
        ans=min(ans,line_to_line(P[yminP],P[yminP+1],Q[ymaxQ],Q[ymaxQ+1]));
        yminP=(yminP+1)%n;
    }
    return ans;
}

int main(){
    int N,M;
    while(~scanf("%d%d",&N,&M)&&N){
        for(int i=0;i<N;i++){
            scanf("%lf%lf",&P[i].x,&P[i].y);
        }
        for(int i=0;i<M;i++){
            scanf("%lf%lf",&Q[i].x,&Q[i].y);
        }
        anticlockwise_sort(P,N);anticlockwise_sort(Q,M);
        printf("%.5lf\n",solve(P,Q,N,M));
    }

    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int maxn=20000+10;
int n,m;
vector<int> G[maxn];
stack<int> S;
int dfs_clock,scc_cnt;
int pre[maxn],low[maxn],sccno[maxn];
bool in0[maxn],out0[maxn];
void dfs(int u)
{
    pre[u]=low[u]=++dfs_clock;
    S.push(u);
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(!pre[v])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccno[v])
            low[u]=min(low[u],pre[v]);
    }
    if(low[u]==pre[u])//强连通分量起点
    {
        scc_cnt++;
        while(true)
        {
            int x= S.top(); S.pop();
            sccno[x]=scc_cnt;
            if(x==u) break;
        }
    }
}
void find_scc(int n)
{
    scc_cnt=dfs_clock=0;
    memset(pre,0,sizeof(pre));
    memset(sccno,0,sizeof(sccno));
    for(int i=0;i<n;i++)
        if(!pre[i]) dfs(i);
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++) G[i].clear();
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            u--, v--;
            G[u].push_back(v);
        }
        find_scc(n);
        for(int i=1;i<=scc_cnt;i++) in0[i]=out0[i]=true;
        for(int u=0;u<n;u++)
        {
            for(int i=0;i<G[u].size();i++)
            {
                int v=G[u][i];
                if(sccno[u] != sccno[v]) out0[sccno[u]]=in0[sccno[v]]=false;
            }
        }
        int a=0,b=0;
        for(int i=1;i<=scc_cnt;i++)
        {
            if(in0[i]) a++;//入度为0
            if(out0[i]) b++;//出度为0
        }
        int ans=max(a,b);
        if(scc_cnt==1) ans=0;
        printf("%d\n",ans);
    }
    return 0;
}

最小球覆盖

#include <iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<cmath>  
using namespace std;  
const double eps=1e-7;  
struct point3D  
{  
    double x,y,z;  
} data[35];  
int n;  
double dis(point3D a,point3D b)  
{  
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));  
}  
double solve()  
{  
    double step=100,ans=1e30,mt;  
    point3D z;  
    z.x=z.y=z.z=0;  
    int s=0;  
    while(step>eps)  
    {  
        for(int i=0; i<n; i++)  
            if(dis(z,data[s])<dis(z,data[i])) s=i;  
        mt=dis(z,data[s]);  
        ans=min(ans,mt);  
        z.x+=(data[s].x-z.x)/mt*step;  
        z.y+=(data[s].y-z.y)/mt*step;  
        z.z+=(data[s].z-z.z)/mt*step;  
        step*=0.98;  
    }  
    return ans;  
}  
int main()  
{ // freopen("t.txt","r",stdin);
    double ans;  
    while(~scanf("%d",&n),n)  
    {  
        for(int i=0; i<n; i++)  
            scanf("%lf%lf%lf",&data[i].x,&data[i].y,&data[i].z);  
        ans=solve();  
        printf("%.5f\n",ans);  
    }  
    return 0;  
}

最小圆覆盖

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
 
using namespace std;
 
const int MAX = 110;
struct point{ double x,y;};
point p[MAX];
const double eps = 1e-6;
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
double disp2p(point a,point b) 
{
	return sqrt( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
}
point l2l_inst_p(point u1,point u2,point v1,point v2)
{
	point ans = u1;
	double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))/
				((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
	ans.x += (u2.x - u1.x)*t;
	ans.y += (u2.y - u1.y)*t;
	return ans;
}
point circumcenter(point a,point b,point c)
{
	point ua,ub,va,vb;
	ua.x = ( a.x + b.x )/2;
	ua.y = ( a.y + b.y )/2;
	ub.x = ua.x - a.y + b.y;//根据 垂直判断，两线段点积为0 
	ub.y = ua.y + a.x - b.x;
	va.x = ( a.x + c.x )/2;
	va.y = ( a.y + c.y )/2;
	vb.x = va.x - a.y + c.y;
	vb.y = va.y + a.x - c.x;
	return l2l_inst_p(ua,ub,va,vb);
} 
void min_circle(point p[],int n,point &c,double &r)
{
	random_shuffle(p,p+n); // 重点 
	c = p[0]; r = 0;
	int cnt = 0;
	for(int i=1; i<n; i++)
		if( dy(disp2p(p[i],c),r) )
		{
			c = p[i]; r = 0;
			for(int k=0; k<i; k++)
				if( dy(disp2p(p[k],c),r) )
				{
					c.x = (p[i].x + p[k].x)/2;
					c.y = (p[i].y + p[k].y)/2;
					r = disp2p(p[k],c);
					for(int j=0; j<k; j++)
						if( dy(disp2p(p[j],c),r) )
						{							// 求外接圆圆心，三点必不共线 
							c = circumcenter(p[i],p[k],p[j]);
							r = disp2p(p[i],c);
						}
				}
		}
}
			
int main()
{
	int n;
	
	while( ~scanf("%d",&n) && n )
	{
		for(int i=0; i<n; i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		point c; double r;
		min_circle(p,n,c,r);
		printf("%.2lf %.2lf %.2lf\n",c.x,c.y,r);
	}
return 0;
}

最小圆覆盖

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
 
#define LL long long
#define PI (acos(-1.0))
#define EPS (1e-10)
 
using namespace std;
 
struct P
{
    double x,y,a;
}p[1100],cp[1100];
 
struct L
{
    P p1,p2;
} line[50];
 
double X_Mul(P a1,P a2,P b1,P b2)
{
    P v1 = {a2.x-a1.x,a2.y-a1.y},v2 = {b2.x-b1.x,b2.y-b1.y};
    return v1.x*v2.y - v1.y*v2.x;
}
 
double Cal_Point_Dis(P p1,P p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}
 
double Cal_Point_Dis_Pow_2(P p1,P p2)
{
    return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}
 
P Cal_Segment_Cross_Point(P a1,P a2,P b1,P b2)
{
    double t = X_Mul(b1,b2,b1,a1) / X_Mul(a1,a2,b1,b2);
    P cp = {a1.x+(a2.x-a1.x)*t,a1.y+(a2.y-a1.y)*t};
    return cp;
}
 
//规范相交
bool Is_Seg_Cross_Without_Point(P a1,P a2,P b1,P b2)
{
    double xm1 = X_Mul(a1,a2,a1,b1);
    double xm2 = X_Mul(a1,a2,a1,b2);
    double xm3 = X_Mul(b1,b2,b1,a1);
    double xm4 = X_Mul(b1,b2,b1,a2);
 
    return (xm1*xm2 < (-EPS) && xm3*xm4 < (-EPS));
}
//向量ab与X轴正方向的夹角
double Cal_Angle(P t,P p)
{
    return ((t.x-p.x)*(t.x-p.x) + 1 - (t.x-p.x-1)*(t.x-p.x-1))/(2*sqrt((t.x-p.x)*(t.x-p.x) + (t.y-p.y)*(t.y-p.y)));
}
//计算 ∠b2.a.b1 的大小
double Cal_Angle_Three_Point(P a,P b1,P b2)
{
    double l1 = Cal_Point_Dis_Pow_2(b1,a);
    double l2 = Cal_Point_Dis_Pow_2(b2,a);
    double l3 = Cal_Point_Dis_Pow_2(b1,b2);
    return acos( (l1+l2-l3)/(2*sqrt(l1*l2)) );
}
bool cmp_angle(P p1,P p2)
{
    return (p1.a < p2.a || (fabs(p1.a-p2.a) < EPS && p1.y < p2.y) ||(fabs(p1.a-p2.a) < EPS && fabs(p1.y-p2.y) < EPS && p1.x < p2.x)   );
}
//p为点集  应该保证至少有三点不共线
//n 为点集大小
//返回值为凸包上点集上的大小
//凸包上的点存储在cp中
int Creat_Convex_Hull(P *p,int n)
{
    int i,top;
    P re; //re 为建立极角排序时的参考点  下左点
    for(re = p[0],i = 1; i < n; ++i)
    {
        if(re.y > p[i].y || (fabs(re.y-p[i].y) < EPS && re.x > p[i].x))
            re = p[i];
    }
 
    for(i = 0; i < n; ++i)
    {
        if(p[i].x == re.x && p[i].y == re.y)
        {
            p[i].a = -2;
        }
        else p[i].a = Cal_Angle(re,p[i]);
    }
    sort(p,p+n,cmp_angle);
    top =0 ;
    cp[top++] = p[0];
    cp[top++] = p[1];
    for(i = 2 ; i < n;)
    {
        if(top < 2 || X_Mul(cp[top-2],cp[top-1],cp[top-2],p[i]) > EPS)
        {
            cp[top++] = p[i++];
        }
                    else
        {
            --top;
        }
    }
 
    return top;
}
 
bool Is_Seg_Parallel(P a1,P a2,P b1,P b2)
{
    double xm1 = X_Mul(a1,a2,a1,b1);
    double xm2 = X_Mul(a1,a2,a1,b2);
 
    return (fabs(xm1) < EPS && fabs(xm2) < EPS);
}
bool Point_In_Seg(P m,P a1,P a2)
{
    double l1 = Cal_Point_Dis(m,a1);
    double l2 = Cal_Point_Dis(m,a2);
    double l3 = Cal_Point_Dis(a1,a2);
    return (fabs(l1+l2-l3) < EPS);
}
//计算三角形外接圆圆心
P Cal_Triangle_Circumcircle_Center(P a,P b,P c)
{
    P mp1 = {(b.x+a.x)/2,(b.y+a.y)/2},mp2 = {(b.x+c.x)/2,(b.y+c.y)/2};
    P v1 = {a.y-b.y,b.x-a.x},v2 = {c.y-b.y,b.x-c.x};
    P p1 = {mp1.x+v1.x,mp1.y+v1.y},p2 = {mp2.x+v2.x,mp2.y+v2.y};
    return Cal_Segment_Cross_Point(mp1,p1,mp2,p2);
}
bool Is_Acute_Triangle(P p1,P p2,P p3)
{
    //三点共线
    if(fabs(X_Mul(p1,p2,p1,p3)) < EPS)
    {
        return false;
    }
    double a = Cal_Angle_Three_Point(p1,p2,p3);
    if(a > PI || fabs(a-PI) < EPS)
    {
        return false;
    }
    a = Cal_Angle_Three_Point(p2,p1,p3);
    if(a > PI || fabs(a-PI) < EPS)
    {
        return false;
    }
    a = Cal_Angle_Three_Point(p3,p1,p2);
    if(a > PI || fabs(a-PI) < EPS)
    {
        return false;
    }
    return true;
}
bool Is_In_Circle(P center,double rad,P p)
{
    double dis = Cal_Point_Dis(center,p);
    return (dis < rad || fabs(dis-rad) < EPS);
}
P Cal_Seg_Mid_Point(P p2,P p1)
{
    P mp = {(p2.x+p1.x)/2,(p1.y+p2.y)/2};
    return mp;
}
void Cal_Min_Circle(P *p,int n)
{
    if(n == 0)
        return ;
    if(n == 1)
    {
        printf("%.2lf %.2lf %.2lf\n",p[0].x,p[0].y,0.00);
        return ;
    }
    if(n == 2)
    {
        printf("%.2lf %.2lf %.2lf\n",(p[1].x+p[0].x)/2,(p[0].y+p[1].y)/2,Cal_Point_Dis(p[0],p[1])/2);
        return ;
    }
    P center = Cal_Seg_Mid_Point(p[0],p[1]),tc1;
    double dis,temp,rad = Cal_Point_Dis(p[0],center),tra1;
    int i,site,a = 0,b = 1,c = 2,d,s1,s2,tp;
    for(dis = -1,site = 0,i = 0; i < n; ++i)
    {
        temp = Cal_Point_Dis(center,p[i]);
        if(temp > dis)
        {
            dis = temp;
            site = i;
        }
    }
 
    while( Is_In_Circle(center,rad,p[site]) == false )
    {
        d = site;
       // printf("a = %d b = %d c = %d d = %d\n",a,b,c,d);
 
        //printf("x = %.2lf  y = %.2lf\n",center.x,center.y);
 
       // printf("rad = %.2lf\n\n",rad);
       // getchar();
 
        double l1 = Cal_Point_Dis(p[a],p[d]);
        double l2 = Cal_Point_Dis(p[b],p[d]);
        double l3 = Cal_Point_Dis(p[c],p[d]);
 
        if((l1 > l2 || fabs(l1-l2) < EPS) && (l1 > l3 || fabs(l1-l3) < EPS))
        {
            s1 = a,s2 = d,tp = b;
        }
        else if((l2 > l1 || fabs(l1-l2) < EPS) && (l2 > l3 || fabs(l2-l3) < EPS))
        {
            s1 = b,s2 = d,tp = c;
        }
        else
        {
            s1 = c,s2 = d,tp = a;
        }
        center = Cal_Seg_Mid_Point(p[s1],p[s2]);
        rad = Cal_Point_Dis(center,p[s1]);
        if( Is_In_Circle(center,rad,p[a]) == false || Is_In_Circle(center,rad,p[b]) == false || Is_In_Circle(center,rad,p[c]) == false )
        {
            center = Cal_Triangle_Circumcircle_Center(p[a],p[c],p[d]);
            rad = Cal_Point_Dis(p[d],center);
            s1 = a,s2 = c,tp = d;
            if(Is_In_Circle(center,rad,p[b]) == false)
            {
                center = Cal_Triangle_Circumcircle_Center(p[a],p[b],p[d]);
                rad = Cal_Point_Dis(p[d],center);
                s1 = a,s2 = b,tp = d;
            }
            else
            {
                tc1 = Cal_Triangle_Circumcircle_Center(p[a],p[b],p[d]);
                tra1 = Cal_Point_Dis(p[d],tc1);
                if(tra1 < rad && Is_In_Circle(tc1,tra1,p[c]))
                {
                    rad = tra1,center = tc1;
                    s1 = a,s2 = b,tp = d;
                }
            }
            if(Is_In_Circle(center,rad,p[c]) == false)
            {
                center = Cal_Triangle_Circumcircle_Center(p[c],p[b],p[d]);
                rad = Cal_Point_Dis(center,p[d]);
                s1 = c,s2 = b,tp = d;
            }
            else
            {
                tc1 = Cal_Triangle_Circumcircle_Center(p[c],p[b],p[d]);
                tra1 = Cal_Point_Dis(p[d],tc1);
                if(tra1 < rad && Is_In_Circle(tc1,tra1,p[a]))
                {
                    rad = tra1,center = tc1;
                    s1 = b,s2 = c,tp = d;
                }
            }
        }
        a = s1,b = s2,c = tp;
        for(dis = -1,site = 0,i = 0;i < n; ++i)
        {
            temp = Cal_Point_Dis(center,p[i]);
            if(temp > dis)
            {
                dis = temp;
                site = i;
            }
        }
    }
    printf("%.2f %.2f %.2f\n",center.x,center.y,rad);
}
 
int main()
{
    int i,n;
    while(scanf("%d",&n) && n)
    {
        for(i = 0;i < n; ++i)
        {
            scanf("%lf %lf",&p[i].x,&p[i].y);
        }
        Cal_Min_Circle(p,n);
    }
}

ZOJ - 4109
题意：n个人，m对朋友，一个人进入party，如果没有朋友在现场，
则此人不开心，设计进party序列，使得不开心人数最少，
且序列按字典序最小
输出最少不开心人数，和进场队列
题解：优先队列+并查集，按连通块分，每个连通块只需要一人不开心即可
并查集合并过程让小的作为父结点
 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define ll long long
const int maxn=1000010;

vector<int> ve[maxn];
int f[maxn];
int n,m;
bool vis[maxn];

void init()
{
	for(int i=0;i<=n;i++){
		f[i]=i;ve[i].clear();
		vis[i]=0;
	}
}
int find1(int x)
{
	return x==f[x]?x:f[x]=find1(f[x]); 
}
void union1(int a,int b)
{
	int fa=find1(a),fb=find1(b);
	if(fa<fb)
		f[fb]=fa;
	if(fa>fb)
		f[fa]=fb;
}
int tot,b[maxn];
void bfs()
{
	priority_queue<int,vector<int>,greater<int> > q;
	int ans=0;
	for(int i=1;i<=n;i++)
		if(i==f[i]){
			ans++;
			vis[i]=1;
			q.push(i);
		}
	tot=0;
	while(!q.empty()){
		int u=q.top();
		q.pop();
		b[tot++]=u;
		for(int i=0;i<ve[u].size();i++){
			int v=ve[u][i];
			if(vis[v]) continue;
			vis[v]=1;
			q.push(v);
		} 
	}
	printf("%d\n",ans);
	for(int i=0;i<tot-1;i++)
		printf("%d ",b[i]);
	printf("%d\n",b[tot-1]); 
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		init();
		int a,b;
		while(m--){
			scanf("%d%d",&a,&b);
			union1(a,b);
			ve[a].push_back(b);
			ve[b].push_back(a);
		}
		bfs();
	} 
	return 0;
}