本文共 4578 字，大约阅读时间需要 15 分钟。

去年省选的题，当时还不会，于是就机智的采用了O(1)算法（输出0），得了10分。

现在想想当时还是太菜了啊……

现在也很菜啊，边连错了好几遍。。。

写这个题还学会了 :: 的用法。。还是太菜了啊。。

废话不多说，题意简单。拆点进行最小割即可

注意连接的边啊，要是考试的时候想出算法然后错在这里可就可惜了

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MAX 1100#define MAXE 150010#define INF 1000000#define S 0#define T ((staff + 1) << 1)using namespace std;struct Point{ int x,y; Point(int a,int b):x(a),y(b) {} Point() {}}a,b,c,d,temp;struct Circle{ Point center; int r; bool Cross(Point st,Point ed);}circle[MAX];struct Square{ Point down,up; bool Cross(Point st,Point ed) { if(InSquare(st) || InSquare(ed)) return true; if(st.x == ed.x) { if(st.x <= up.x && st.x >= down.x) if(st.y <= down.y && st.y >= up.y) return true; } else { if(st.y <= up.y && st.y >= down.y) if(st.x <= down.x && ed.x >= up.x) return true; } return false; } bool InSquare(Point a) { if(a.x <= up.x && a.x >= down.x && a.y <= up.y && a.y >= down.y) return true; return false; }}square[MAX];int staff,points;int circles,squares;int head[MAX],total = 1;int next[MAXE],aim[MAXE],flow[MAXE];int deep[MAX];inline double Calc(Point a,Point b);inline void Add(int x,int y,int f);bool BFS();int Dinic(int x,int f);Point MakePoint(int x,int y);int main(){ cin >> c.x >> c.y >> staff; b.x = b.y = 0; a.x = 0,a.y = c.y; d.y = 0,d.x = c.x; for(int flag,i = 1;i <= staff; ++i) { scanf("%d",&flag); if(flag == 1) { scanf("%d%d",&temp.x,&temp.y); circle[++circles].center = temp; scanf("%d",&circle[circles].r); } else { scanf("%d%d",&temp.x,&temp.y); square[++squares].down = temp; scanf("%d%d",&temp.x,&temp.y); square[squares].up = temp; } } for(int i = 1;i <= circles; ++i) { Add(i << 1,i << 1|1,1); if(circle[i].Cross(a,c)) Add(S,i << 1,INF); if(circle[i].Cross(b,d)) Add(i << 1|1,T,INF); } for(int i = 1;i <= squares; ++i) { Add((i + circles) << 1,(i + circles) << 1|1,1); if(square[i].Cross(a,c)) Add(S,(i + circles) << 1,INF); if(square[i].Cross(b,d)) Add((i + circles) << 1|1,T,INF); } for(int i = 1;i <= circles; ++i) for(int j = i + 1;j <= circles; ++j) if((Calc(circle[i].center,circle[j].center) <= circle[i].r + circle[j].r)) Add(i << 1|1,j << 1,INF),Add(j << 1|1,i << 1,INF); for(int i = 1;i <= squares; ++i) for(int j = i + 1;j <= squares; ++j) { bool flag = true; Point st = square[j].down,ed = square[j].up; if(square[i].Cross(st,MakePoint(ed.x,st.y))) flag = false; if(square[i].Cross(st,MakePoint(st.x,ed.y))) flag = false; if(square[i].Cross(MakePoint(st.x,ed.y),ed)) flag = false; if(square[i].Cross(MakePoint(ed.x,st.y),ed)) flag = false; if(!flag) { Add((i + circles) << 1|1,(j + circles) << 1,INF); Add((j + circles) << 1|1,(i + circles) << 1,INF); } } for(int i = 1;i <= circles; ++i) for(int j = 1;j <= squares; ++j) { bool flag = true; Point st = square[j].down,ed = square[j].up; if(circle[i].Cross(st,MakePoint(ed.x,st.y))) flag = false; if(circle[i].Cross(st,MakePoint(st.x,ed.y))) flag = false; if(circle[i].Cross(MakePoint(st.x,ed.y),ed)) flag = false; if(circle[i].Cross(MakePoint(ed.x,st.y),ed)) flag = false; if(!flag) { Add(i << 1|1,(j + circles) << 1,INF); Add((j + circles) << 1|1,i << 1,INF); } } int max_flow = 0,temp; while(BFS()) while(temp = Dinic(S,INF),temp) max_flow += temp; cout << max_flow; return 0;}inline double Calc(Point a,Point b){ return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y));}inline void Add(int x,int y,int f){ next[++total] = head[x]; aim[total] = y; flow[total] = f; head[x] = total; next[++total] = head[y]; aim[total] = x; flow[total] = 0; head[y] = total;}bool BFS(){ static queue
         
           q; while(!q.empty()) q.pop(); memset(deep,0,sizeof(deep)); deep[S] = 1; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x];i;i = next[i]) if(flow[i] && !deep[aim[i]]) { deep[aim[i]] = deep[x] + 1; q.push(aim[i]); if(aim[i] == T) return true; } } return false;}int Dinic(int x,int f){ if(x == T) return f; int temp = f; for(int i = head[x];i;i = next[i]) if(flow[i] && deep[aim[i]] == deep[x] + 1 && temp) { int away = Dinic(aim[i],min(flow[i],temp)); if(!away) deep[aim[i]] = 0; flow[i] -= away; flow[i^1] += away; temp -= away; } return f - temp;}bool Circle :: Cross(Point st,Point ed) { if(st.x == ed.x) { if(center.y <= ed.y && center.y >= st.y) return abs(center.x - st.x) <= r; return (Calc(center,st) <= r || Calc(center,ed) <= r); } else { if(center.x <= ed.x && center.x >= st.x) return abs(center.y - st.y) <= r; return (Calc(center,st) <= r || Calc(center,ed) <= r); }}Point MakePoint(int x,int y){ Point a(x,y); return a;}
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/jiangyuze831/article/details/38930033 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！