题目链接→

s,n 1e9的范围直接暴力匹配二分图肯定会T。。。

对于区间[1,n]和[s+1,s+n]，如果存在重叠部分，

                                                                           比如1,2,3......,n-2,   n-1 ,  n

                                                                                                    ↓      ↓      ↓

                                                                                                  s+1,s+2,s+3......s+n 

                                                       s+1,s+2,s+2直接放在s+1,s+2,s+3的位置，只需要去匹配[1,s]和[n,s+n]

这样，我们需要去匹配的区间内就没有s+i可以放在s+i位置的了，如果区间内存在>=2个素数，这些素数只能放在第一个位置，这种情况肯定是No

对于2e9内的数据，打个表可以发现，两个素数间的最大距离为220？还是多少来着，也就是说，如果需要匹配的区间范围超过>440（这里用的450，没啥区别感觉）

的情况肯定也是No，这样我们进行二分图匹配的最大区间范围就缩小到了450，然后就直接用匈牙利算法去进行二分图匹配   get√

边的话……就暴力，可以整除就加边，嗯。

顺便补一补二分图匹配的相关知识，戳这些→

       好多博客写的都很棒啊，这里码几篇        （这里有匈牙利和km）

            万能度娘                                          

                                                                     

                                                                   

#include
     
      using namespace std;typedef long long ll;const int MAX=450; //<--匈牙利-->   二分图匹配 int t,n,s,cas=1;vector
      
       e[MAX];map
       
        match; //存储求解结果 map
        
         check;bool dfs(int u){    for(auto v:e[u])    {        if(!check[v])        {            check[v]=1;            if(!match[v]||dfs(match[v]))            {                match[v]=u;                return 1;            }        }    }    return 0;}int hungarian(){    int ans=0;    match.clear();    for(int u=1;u<=n;u++)    {        if(!match[u])        {            check.clear();            if(dfs(u))            ans++;        }    }    return ans;}int main(){    cin>>t;    while(t--)    {        for(int i=0;i
         
          >n>>s;        if(s
          
           MAX){ cout<<"Case #"<
           
            <<": No"<
           
          
         
        
       
      
     

 

码板子码板子

hungarian

DFS

vector
     
      edge[MAX];  //邻接表存储边集map
      
       match;     //匹配标记 map
       
        vis;       //是否在交替路中bool dfs(int u){  for(auto v:edge[u])  //在u的邻接点中查询  {      if(!vis[v])   //不在交替路中     {          vis[v]=1; //加入到交替路中         if(!match[v]||dfs(match[v]))   //为增广路,交换路径，匹配边+1         {          match[v]=u;          match[u]=v;          return true;         }     }   }      return false; //不存在增广路 } int hungarian(){  int ans=0;  match.claear();  for(int u=0;u
       
      
     

BFS

queue
     
      q;int prev[MAX];  //保存路径 vector
      
       e[MAX];map
       
        match;map
        
         vis;int hungarian(){    int ans=0;    match.clear();    vis.clear();    for(int u=1;u<=left_n;u++)    if(!match[i])    {     while(!q.empty())      q.pop();     q.push(u);     prev[u]=0; //u为起点     bool flag=false;//是否找到增广路      while(!q.empty()&&!flag)      {         int s=q.front();        for(auto v:e[s])        {            if(vis[v]!=u)            {                vis[v]=u;                q.push(match[v]);                if(match[v])                 prev[match[v]]=u;                else //v为未匹配点,交替路变增广路                 {                    flag=true;                    int d=s,f=v;                    while(d)                    {                        int temp=match[d];                        match[d]=f;                        match[f]=d;                        d=prev[d];                        f=temp;                    }                }            }              }         q.pop();      }           if(match[u]) ans++;     }    return ans; }
        
       
      
     

 KM

最佳匹配（带权二分图）

#include
     
      using namespace std;const int MAX=1e5;int w[MAX][MAX];int match[MAX],usex[MAX],usey[MAX],cx[MAX],cy[MAX];//match记录右边端点所连的左端点，usex，usey判断是否在增广路上，cx，cy为记录点的顶标int n,ans,m;bool dfs(int x){  usex[x]=1;  for(int i=1;i<=m;i++)  {      if(!usey[i]&&cx[x]+cy[i]==w[x][i])      {                     //如果i未被访问过且为子图的边         usey[i]=1;      if(!match[i]||dfs(match[i]))          {                    //若为未匹配点或匹配点可改        match[i]=x;       return true;       }     }  }  return false;    } int km(){    for(int i=1;i<=n;i++)    {        while(1)        {            int d=MAX;            memset(usex,0,sizeof(usex));            memset(usey,0,sizeof(usey));            if(dfs(i)) break; //匹配成功 继续匹配其他点             for(int j=1;j<=n;j++)            {                if(usex[j])                 for(int k=1;k<=m;k++)                     if(!usey[k])                      d=min(d,cx[j]+cy[k]-w[j][k]);            }            if(d==MAX) return -1;            for(int j=1;j<=n;j++)                if(usex[j]) cx[j]-=d;            for(int j=1;j<=m;j++)                if(usey[j]) cy[j]+=d;  //添加新边         }    }    ans=0;    for(int i=0;i<=m;i++)     ans+=w[match[i]][i];    return ans;  } int main(){    while(cin>>n>>m)    {        memset(cx,0,sizeof(cx));        memset(cy,0,sizeof(cy));        memset(w,0,sizeof(w));        for(int i=1;i<=n;i++)        {            int d=0;            for(int j=1;j<=m;j++)             {              cin>>w[i][j];              d=max(d,w[i][j]);            }            cx[i]=d;        }         memset(match,0,sizeof(match));        cout<
      
       <