题意:给一段子序列,定义密度:子序列中的逆序对数/子序列的长度

求这个序列的对大密度.

分析:将序列中的每个位置视作点,逆序对\(<i,j>\)之间表示点i与点j之间有一条无向边.所以就转化为了最大密度子图的模型.

#include
    
     using namespace std;#define eps 1e-7#define INF 0x3f3f3f3fconst int MAXN=1010;//点数的最大值const int MAXM=400010;//边数的最大值#define captype doublestruct Edge{    int from,to,next;    captype cap;};struct SAP_MaxFlow{    Edge edges[MAXM];    int tot,head[MAXN];    int gap[MAXN];    int dis[MAXN];    int cur[MAXN];    int pre[MAXN];    void init(){        tot=0;        memset(head,-1,sizeof(head));    }    void AddEdge(int u,int v,captype c,captype rc=0){        edges[tot] = (Edge){u,v,head[u],c};  head[u]=tot++;        edges[tot] = (Edge){v,u,head[v],rc}; head[v]=tot++;    }    captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意        memset(gap,0,sizeof(gap));        memset(dis,0,sizeof(dis));        memcpy(cur,head,sizeof(head));        pre[sNode] = -1;        gap[0]=n;        captype ans=0;        int u=sNode;        while(dis[sNode]
     
      edges[i].cap){                    Min=edges[i].cap;                    inser=i;                }                for(int i=pre[u]; i!=-1; i=pre[edges[i^1].to]){                    edges[i].cap-=Min;                    edges[i^1].cap+=Min;                }                ans+=Min;                u=edges[inser^1].to;                continue;            }            bool flag = false;            int v;            for(int i=cur[u]; i!=-1; i=edges[i].next){                v=edges[i].to;                if(edges[i].cap>0 && dis[u]==dis[v]+1){                    flag=true;                    cur[u]=pre[v]=i;                    break;                }            }            if(flag){                u=v;                continue;            }            int Mind= n;            for(int i=head[u]; i!=-1; i=edges[i].next)            if(edges[i].cap>0 && Mind>dis[edges[i].to]){                Mind=dis[edges[i].to];                cur[u]=i;            }            gap[dis[u]]--;            if(gap[dis[u]]==0) return ans;            dis[u]=Mind+1;            gap[dis[u]]++;            if(u!=sNode)  u=edges[pre[u]^1].to;  //退一条边        }        return ans;    }}F;int N, M;int S,T;int deg[MAXN];int ed[MAXM][2];bool check(double mid){    F.init();    S = 0, T = N+1;    for(int i=1;i<=N;++i){        F.AddEdge(S,i,M*1.0);        F.AddEdge(i,T,1.0*M + 2*mid - deg[i]);    }    for(int i=1;i<=M;++i){        F.AddEdge(ed[i][0],ed[i][1], 1.0);        F.AddEdge(ed[i][1],ed[i][0], 1.0);    }    double hg = ( 1.0 * M * N - F.maxFlow_sap(S,T,T+1)) *0.5;    return hg>eps;}int p[MAXN];int main(){    #ifndef ONLINE_JUDGE        freopen("in.txt", "r", stdin);        freopen("out.txt", "w", stdout);    #endif    int u,v;    int T,cas=1; scanf("%d",&T);    while(T--){        printf("Case #%d: ",cas++);        scanf("%d",&N);        for(int i=1;i<=N;++i) scanf("%d",&p[i]);        M = 0 ;        memset(deg,0,sizeof(deg));        for(int i=1;i<=N;++i){            for(int j=i+1;j<=N;++j){                if(p[i]>p[j]){                    M ++;                    ed[M][0] = i, ed[M][1] = j;                    deg[i]++, deg[j]++;                }            }        }        double L = 0.0, R = M*1.0;        while(R-L>= eps){            double mid = (R+L)*0.5;            if(check(mid)){                L = mid;            }else{                R = mid;            }        }        printf("%.7f\n",L);    }    return 0;}