CodeChef Poetic word

CodeChef Poetic word

转自：
题目链接：
题意：输入要构造的单词长度，输入26个字母的个数，从a开始给26个字母分别编号为idx=1、2……，设字母在单词的位置为pos(从1开始)，则字母能放在pos%idx的地方，求字典序最小的单词。
思路：网络流。字典序最小的情况一定是从编号最小的字母开始放置。重点是如何建图。 暴力枚举每一个位置，然后枚举每一个字母是否可以放置。在判断当前字母能否放置时，如果能够放置在这个地方，就把这个位置和这个字母连一条边，容量为1(因为这个位置只能放置一个字母)。源点与每个字母连一条边，容量是字母的个数（这个可以理解），汇点与位置相连，容量为1（如果有字母可以放置到剩下的位置上，应该为答案贡献1）.跑一边最大流，最大流的结果是剩下的字母能够放置进单词的个数，看是否与剩下的位置相等。如果相等，就说明可以放置。不行就回溯。

#include <bits/stdc++.h>
using namespace std;
const int maxn=500;
const int inf1=1e9+5;
int source,sink,n;
int num[30];
struct edge
{int from,to,cap,flow;
};
struct dinic
{int n, m,s,t;vector <edge> gg;vector <int> ggg[maxn];bool vis[maxn];int d[maxn];int cur[maxn];void init(int l){gg.clear();for(int i=0; i<=l; i++){ggg[i].clear();}}void add(int from,int to,int cap){gg.push_back((edge){from,to,cap,0});gg.push_back((edge){to,from,0,0});m=gg.size();ggg[from].push_back(m-2);ggg[to].push_back(m-1);}bool bfs(){memset(vis,0,sizeof(vis));queue<int> q;q.push(s);d[s]=0;vis[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=0; i<ggg[x].size(); i++){edge &e=gg[ggg[x][i]];if(!]&&e.cap>e.flow){]=1;]=d[x]+1;q.);}}}return vis[t];}int dfs(int x,int a){if(x==t||a==0){return a;}int flow=0,f;for(int &i=cur[x]; i<ggg[x].size(); i++){edge &e=gg[ggg[x][i]];if(d[x]+1==]&&(f=,min(a,e.cap-e.flow)))>0){e.flow+=f;gg[ggg[x][i]^1].flow-=f;flow+=f;a-=f;if(a==0)break;}}return flow;}int maxflow(int s,int t){this->s=s;this->t=t;int flow=0;while(bfs()){memset(cur,0,sizeof(cur));flow+=dfs(s,inf1);}return flow;}
} din;
bool judge(int idx)
{din.init(500);//初始化for(int i=1; i<=26; i++){for(int j=idx+1; j<=n; j++){if(j%i==0){din.add(i,j+26,1);//i代表字母 j代表位置 j+26防止字母与位置的点}                      //相同导致冲突}din.add(source,i,num[i]);//与源点建边}for(int i=idx+1; i<=n; i++){din.add(i+26,sink,1);//与汇点建边}return din.maxflow(source,sink)==n-idx;//最大流的结果就是剩余字母能够放进
}                                         //的位置数
int main()
{int T;scanf("%d",&T);while(T--){source=0;//增加源点与汇点sink=300;scanf("%d",&n);for(int i=1; i<=26; i++){scanf("%d",&num[i]);}if(!judge(0))//先什么也不限制跑一边看是否有答案{puts("#rekt");}else{string ans="";for(int i=1; i<=n; i++){for(int j=1; j<=26; j++){if(num[j]>0&&i%j==0)//这个字母可以放置到这个位置上{num[j]--;if(judge(i))//判断{ans+='a'+j-1;//统计答案break;}num[j]++;//回溯}}}cout<<ans<<endl;}}return 0;
}