https://vjudge.net/problem/49919/origin

题意：给你n*n只出现O和X的字符阵。有两种操作，一种操作Ri将i行全变成X,一种操作Ci将i列全变成O，每个不同的操作最多进行一次。现给出目标状态，求空盘下的字典序最小的操作顺序是怎样的。

思路：拿到题目看起来很复杂，但仔细读题会发现X和O只由特定操作出现，且操作只进行一次，那么单独地考虑每行每列，如i行中出现了O，且存在X（如果不存在X那么可以略去Ri操作），说明在Ri操作后进行了Cj的操作，同样的方法去考虑列，就能得到所有需要进行的行列操作相对顺序。这显然是个拓扑结构。那么将行操作或列操作看作点，建图拓扑排序即可。

关键还是在于建模，vijos上有道很相像的题目(1030)，但比这道复杂一些还需要DFS。但是这道省赛题由于要求的复杂度不太严格，还可以模拟做。

但我居然一下子没有想出来用拓扑排序orz

weak-dish?

/** @Date    : 2017-03-27-21.44  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version :  */#include<bits/stdc++.h>#define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;const int ost = 510;char mp[510][510];vectorvt[1100];int fr[510], fc[510];int cnt[1100];int n;void init(){    MMF(fr);    MMF(fc);    MMF(cnt);    for(int i = 0; i < n + ost; i++)        vt[i].clear();    for(int i = 0; i < n; i++)    {        for(int j = 0; j < n; j++)        {            if(mp[i][j] == ‘O‘)                fc[j] = 1;            else fr[i] = 1;        }    }    for(int i = 0; i < n; i++)    {        if(!fr[i]) continue;        for(int j = 0; j < n; j++)        {            if(mp[i][j] == ‘O‘)                vt[i].PB(j + ost), cnt[j + ost]++;        }    }    for(int j = 0; j < n; j++)    {        if(!fc[j]) continue;        for(int i = 0; i < n; i++)        {            if(mp[i][j] == ‘X‘)                vt[j + ost].PB(i), cnt[i]++;        }    }}void top(){    int ct = 0;    priority_queue<int, vector, greater >q;    for(int i = 0; i < n + ost; i++)    {        if(cnt[i] == 0 && vt[i].size() != 0)            q.push(i);    }    while(!q.empty())    {        int nw = q.top();        q.pop();        for(int i = 0; i < vt[nw].size(); i++)        {            int nt = vt[nw][i];            cnt[nt]--;            if(!cnt[nt])                q.push(nt);        }        if(nw < ost)            printf("%sR%d", ct==0?"":" ", nw + 1), ct = 1;        else printf("%sC%d", ct==0?"":" ", nw - ost + 1), ct = 1;    }    if(ct == 0)        printf("No solution");    printf("\n");}int main(){    int T;    cin >> T;    while(T--)    {        cin >> n;        for(int i = 0; i < n; i++)        {            scanf("%s", mp[i]);        }        init();        top();    }    return 0;}

ZOJ 3780 E - Paint the Grid Again 拓扑排序