[luogu8291]学术社区

对所有消息建图，图中包含以下两类边：

1.对于楼上消息，假设其提到的网友为$s$，其向$s$发出的消息连边

2.对于楼下消息，假设其提到的网友为$s$，$s$发出的消息向其连边

关于边$(x,y)$的含义，即消息$x$的下一条消息为$y$?时有1的收益

在此基础上，问题即选择若干条无公共点的简单路径，最大化收益和

另外，特殊性质$C$中的情况会产生重边，此时选该边的收益为2

结论1：对于重边$(x,y)$，存在一种最优方案选择该边

任取一组最优解，对其分类讨论：

1.若其中$x$的出边或$y$的入边收益为2，不妨交换$y/x$和该点

2.若其中$x$的出边和$y$的入边收益均不为2，直接用$(x,y)$替换不劣

根据此结论，可以将图中$x$的出边和$y$的入边均删除，并将最终答案$+2$

此时，图中所有边的收益均为$1$，进而问题也即转换为最小路径覆盖

结论2：将该图视作DAG求最小路径覆盖，答案不变

对于通常的有向图，该做法问题在于可能选择一个简单环

注意到简单环中总包含非学术消息（学术消息之间无边），不妨假设包含楼上消息

楼上消息的入边（另一个端点）必然也为楼上消息，以此类推整个环均为楼上消息

此时，任取图中某个消息，在该处断开并插入对应的学术消息前即可

重复上述过程，最终可得一组不包含简单环的方案，即得证

根据此结论，并在建图时简单优化建边即可

由于二分图至多增广$\sqrt{m}$次，总复杂度为$o(m\sqrt{m})$，可以通过

建边时使用vector会比邻接表快很多，可能是出边顺序的问题

  1 #include
  2 using namespace std;
  3 #define N 80000
  4 #define M 1000000
  5 #define ull unsigned long long
  6 int t,n,m,a[N],b[N],c[N];ull s1,s2,s3,id[N];
  7 int V,E,it[M],d[M];queue<int>q;struct Data{int to,len,rev;};vectore[M];
  8 int ans,pos[N],vis[N],pre[N],nex[N];vector<int>vl,vr;map<int,vector<int> >mat1[N],mat2[N];
  9 int change(char c){
 10     if ((c>='A')&&(c<='Z'))return c-'A'+1;
 11     if ((c>='a')&&(c<='z'))return c-'a'+27;
 12     if (c=='_')return 53;
 13     if (c=='?')return 54;
 14     if (c=='!')return 55;
 15     return (c=='.' ? 56 : 0);
 16 }
 17 ull read(){
 18     ull x=0;int c=change(getchar());
 19     while (!c)c=change(getchar());
 20     while (c)x=x*57+c,c=change(getchar());
 21     return x;
 22 }
 23 void add(int x,int y,int z){
 24     e[x].push_back(Data{y,z,(int)e[y].size()});
 25     e[y].push_back(Data{x,0,(int)e[x].size()-1});
 26 }
 27 bool bfs(){
 28     for(int i=1;i<=V;i++)d[i]=-1;
 29     q.push(0);
 30     while (!q.empty()){
 31         int k=q.front();q.pop();
 32         for(Data i:e[k])
 33             if ((i.len)&&(d[i.to]<0))d[i.to]=d[k]+1,q.push(i.to);
 34     }
 35     return d[V]>=0;
 36 }
 37 int dfs(int k,int s){
 38     if (k==V)return s;
 39     int ans=0;
 40     for(int &i=it[k];i)
 41         if ((e[k][i].len)&&(d[e[k][i].to]==d[k]+1)){
 42             int p=dfs(e[k][i].to,min(s,e[k][i].len));
 43             e[k][i].len-=p,e[e[k][i].to][e[k][i].rev].len+=p,s-=p,ans+=p;
 44             if (!s)return ans;
 45         }
 46     return ans;
 47 }
 48 int dinic(){
 49     int ans=0;
 50     while (bfs()){
 51         ans+=dfs(0,0x3f3f3f3f);
 52         for(int i=0;i<=V;i++)it[i]=0;
 53     }
 54     return ans;
 55 }
 56 void link(int x,int y){
 57     if (nex[x])pre[nex[x]]=0;
 58     if (pre[y])nex[pre[y]]=0;
 59     nex[x]=(x ? y : 0),pre[y]=(y ? x : 0);
 60 }
 61 int main(){
 62     scanf("%d",&t);
 63     while (t--){
 64         scanf("%d%d",&n,&m);
 65         V=(m+n<<1)+1,E=ans=0;
 66         for(int i=0;i<=V;i++)it[i]=0,e[i].clear();
 67         for(int i=1;i<=m;i++)vis[i]=pre[i]=nex[i]=0;
 68         for(int i=1;i<=n;i++)mat1[i].clear(),mat2[i].clear();
 69         for(int i=1;i<=n;i++)id[i]=read();
 70         sort(id+1,id+n+1);
 71         for(int i=1;i<=m;i++){
 72             s1=read(),s2=read(),s3=read();
 73             a[i]=lower_bound(id+1,id+n+1,s1)-id;
 74             b[i]=lower_bound(id+1,id+n+1,s2)-id;
 75             if ((b[i]>n)||(id[b[i]]!=s2))b[i]=c[i]=0;
 76             else c[i]=(s3==23305962750LL ? 2 : (s3==75721020011865LL));
 77             if (!c[i])pos[a[i]]=i;
 78             if (c[i]==1){
 79                 if (mat2[b[i]][a[i]].empty())mat1[a[i]][b[i]].push_back(i);
 80                 else{
 81                     int j=mat2[b[i]][a[i]].back();
 82                     mat2[b[i]][a[i]].pop_back();
 83                     ans+=2,link(i,j),vis[i]=vis[j]=1;
 84                 }
 85             }
 86             if (c[i]==2){
 87                 if (mat1[b[i]][a[i]].empty())mat2[a[i]][b[i]].push_back(i);
 88                 else{
 89                     int j=mat1[b[i]][a[i]].back();
 90                     mat1[b[i]][a[i]].pop_back();
 91                     ans+=2,link(j,i),vis[i]=vis[j]=1;
 92                 }
 93             }
 94         }
 95         for(int i=1;i<=m;i++){
 96             add(0,i,1),add(i+m,V,1);
 97             if ((!vis[i])||(c[i]!=1))add(i,a[i]+(m<<1),1);
 98             if ((!vis[i])||(c[i]!=2))add(a[i]+(m<<1)+n,i+m,1);
 99             if ((!vis[i])&&(c[i]==1))add(i,b[i]+(m<<1)+n,1);
100             if ((!vis[i])&&(c[i]==2))add(b[i]+(m<<1),i+m,1);
101         }
102         ans+=dinic(),printf("%d\n",ans);
103         for(int i=1;i<=n;i++){
104             for(Data j:e[i+(m<<1)+n])e[i+(m<<1)].push_back(j);
105             for(Data j:e[i+(m<<1)]){
106                 if ((j.to<=m)&&(j.len)){
107                     if (vr.empty())vl.push_back(j.to);
108                     else link(j.to,vr.back()),vr.pop_back();
109                 }
110                 if ((j.to>m)&&(!j.len)){
111                     if (vl.empty())vr.push_back(j.to-m);
112                     else link(vl.back(),j.to-m),vl.pop_back();
113                 }
114             }
115         }
116         for(int i=1;i<=m;i++)vis[i]=0;
117         for(int i=1;i<=m;i++)
118             if (!vis[i]){
119                 int j=i;
120                 while (!vis[j])vis[j]=1,j=nex[j];
121                 if (j==i){
122                     if (c[i]==1)j=pre[i],link(pre[pos[a[i]]],i),link(j,pos[a[i]]);
123                     else j=nex[i],link(i,nex[pos[a[i]]]),link(pos[a[i]],j);
124                 }
125             }
126         for(int i=1;i<=m;i++)
127             if (!pre[i]){
128                 for(int j=i;j;j=nex[j])printf("%d ",j);
129             }
130         printf("\n");
131     }
132     return 0;
133 }